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.