Double-signature paper wallets?
This is basically correct. Your main challenge is that the current way to do multisig transactions references the public keys rather than just the addresses. Therefore when you generate the paper wallets, you need to take note of the public keys. Then you can input those into the bitcoin-qt console to generate the multisig address (there's a worked example by Gavin).

Note that using the funds in the multisig does not require the two private keys to exist together in the same machine, rather you just need to generate a signature using each (on separate machine).