I am one week away from releasing an alpha version of Armory
which does exactly
what you are requesting. The only thing remaining is the dialogs that allows the user to easily sign transactions using the offline wallets. Armory will be the best program for offline transactions, miles ahead of all other attempts! You won't even need to keep the blockchain on the offline computer!
Here's a screenshot of the "Paper Backup" dialog:
You only need to print it once, when the wallet is first created, and it will serve as a permanent backup for the deterministic wallets. Also, you can create such a wallet on the offline computer, then "Make a watching-only" wallet which can be copied to the online computer and can be used to generate addresses and verify payments, but does not have access to the private keys.
If you want to get in on early testing, let me know