I personally love how Electrum wallet does it:
You may generate and regenerate wallet using only key word phrase. Keep it safe in memory or in bank deposit box.
No backups needed. You may always regenerate wallet by keyphrase.
With Electrum you have to have a fully trusted machine to sign transactions. Using M-of-N multisig transaction is safe even if NSA secretly owns your machine.
Doesn't Electrum do this by backing up your wallet to "the cloud"? Even if it is 100% properly encrypted, I can't say that I feel good about this. Feels like one bug away from compromising many people's wallets.
https://electrum.org/seed.html
The screenshot uses ecdsa.org, which seems to be just an Electrum server of some kind.
https://en.bitcoin.it/wiki/Thin_Client_Security
It knows which transactions are relevant because of the keys that can be deterministically generated from your seed, but the seed itself isn't sent to a server.