For power users, if they forget their pw, they lose their coins. Period. That's the option I would use, as someone who never lost an important pw thanks to my use of redundant password safes.
For other users, when creating an account, coinbase.com could email them a "key recovery" file (or mail them a physical QR code), with instructions to keep it permanently stored in a safe place. This key recovery file would be K encrypted with a unique IV and a key known by coinbase.com, who would not keep a copy of the key recovery file. This would satisfy all my requirements: coinbase.com would be unable to steal/access the users coins, and an attacker merely getting access to the key recovery file would be unable to do anything with it.
Like file system encryption is done. You don´t encrypt the hard drive with your pass phrase. You encrypt the encryption key to your hard drive with your passphrase. Your problem is solved with an extra key in offline storage.
In this case instead of just encrypting private keys with K (derived from user's password), you encrypt private keys with K and encrypt K with user's password. You also encrypt K with your own master key which is stored offline. You could either retrieve K manually or through a rate-limited API.
However, Estragons point about it only slowing down the attack still holds, although in Bitcoinicas case the loss would be much less, since they discovered the attack early. "not even you(!)" however is false.
