Multisig Wallet vs Hot and Cold Wallets

Exchanges and web wallets do not need "cold" and "hot" storage. They need 2-of-3 multisig lock.

1. User's funds are locked on 2-of-3 multisig transaction (P2SH or directly, does not matter).

2. Key A belongs to user (similarly to Blockchain.info, service may backup the encrypted key, but user loses key when forgets the password).

3. Key B is stored on web server, unencrypted.

4. Key C belongs to technical staff of the service. This key is encrypted by staff's password and only stored on personal computers of the staff.

"Hot storage" is a combination of key A and key B: user can withdraw (possibly limited) amount of coins immediately. Coinbase does not risk losing hot wallet funds. Bitcoin-Central does not need to disable immediate withdrawals.

"Cold storage" is a combination of key B and C: user may lose password, but can contact the support staff to unlock his funds. This solves the problem of Blockchain.info, where users must never forget their passwords.

Note: this breaks Blockchain.info's promise to never have access to anyone's funds. But if your own web wallet wants to nanny its users, then that's the solution for you.

The only downside: user needs to take care of storing their key somewhere. The way Blockchain.info does it is not entirely safe as attacker who gains access to their server may place a honeypot collecting users' passwords. Some standalone installable app would be helpful.