This is only really useful for large sums of money IMO. I think it might be better to offer truly offline "storage wallets". When the user wants their wallet, you send them a copy GPG-encrypted to them along with a LiveCD for safely accessing the wallet. Obviously this is high-latency. There have been better solutions proposed, but in the short term this would work.

You'll need to build some trust, yes. I wonder, since I use my real name, have been around since the $0.06 days, and have a good trust rating in the forums, how much would people trust me to store their wallets? What if I did it through my company?