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?
Meatspace storage of wallets would be a good idea for very large sums of money, but I think most people are better off doing this themselves through a bank safe deposit box. It's also a very customer service intensive business and requires hiring a lot of staff.
Not that hard actually:
1. Write a script that creates a wallet, dumps an address from it, encrypts it, and then creates another wallet etc.
2. Keep list of addresses.
3. When someone wants to open an account, give them the address.
4. When they want to withdraw, decrypt wallet, encrypt to them, put on flash drive, mail.
5. When they confirm receipt, shred original.