If you held a pre-signed transaction that sends the funds back to you with a lockTime of 1 Jan 2013 that would work.
Lets see... thinking out loud...
Start by asking the exchange for a brand-new public key to use for their half of the 2-of-2 transaction. Call the send-coins-into-2-of-2 transaction "F" (for Fund).
You create and sign that transaction, but don't broadcast it yet.
Use it's transaction id to create a second, one-input-two-signature, lockTime=1/1/2013 transaction that refunds the coins to you. Call that "R" (for Refund).
Send R to the exchange and ask them to sign it using that brand-new public key they gave you. The exchange checks the lockTime and then returns R and the signature to you. You check the signature, and if it is good, broadcast F (and keep the half-signed R someplace safe).
If 1/1/2013 rolls around and you want your coins back, you sign your half of R and broadcast it.
I'd have to think a little harder than I want to right now about whether or not signing R knowing only txid==HASH(F) opens up the exchange to attacks. I can't think of any, but the exchange providing a signature when it doesn't know the details of exactly what it is signing makes me nervous.That should be safe if and only if a unique key is used to sign, and you can be absolutely certain that it has not nor will not be used for anything else until the exchange receives the signed transaction F. That means that the key can't be from a pre-generated list that may have been backed up, because that backup might eventually need to be used and the key could unknowingly be used for something else. It'd be a hard attack to pull off, but the potential for an attack is certainly there. So, the exchange would need to generate the key for signing transaction R on-the-fly and mark it specifically for this purpose. Thus, there's no risk that the key might be used for something else once it is backed up. If F is never sent then, the worst-case scenario is that a brand-new key will have only ever signed one transaction and never received anything. Since the key would have to be newly-generated, the worst-case scenario is that the exchange loses that key but you still have a signed transaction to get your money back later, anyway.
I think holding on to pre-signed-but-not-broadcast-yet transactions is a technique "we" don't think about enough.
That being said, I also have a more general-case solution that will allow this technique to work in all cases...
You could send the unsigned R and the signed-but-not-broadcast F to the exchange and trust that the exchange will not broadcast F unless they agree to sign R.
Generally that may be safe, but there's a chance that your money might fall into the void. So, the problem here is that F needs to be invalid when we send it to the exchange, but needs to be able to be made valid without changing anything in the transaction, meaning that we can't withhold signatures. So, let's just not withhold anything in
this transaction at all. The very problem we're seeing here is actually it's own solution: the exchange doesn't want to sign something when it only knows the hash of an input transaction, but not the input transaction itself. It's the same for miners: they need the input transactions, not just the hashes, to enter a transaction into the blockchain.
So, the user just needs to not tell anyone about "Fi", an input to "F", until they get back "R". If "F" is broadcast and "R" is never signed, it's okay, because "F" was just an orphan and will never hit the blockchain unless the user broadcasts "Fi".