I have a Nexus S running WhisperCore (a ROM with built in encryption) with the bitcoin wallet app.
WhisperCore comes with a backup program called Flashback that will encrypt and upload data to Amazon S3 storage.
Titanium Media Sync is also a good alternative as it will enable you to select files individually (+you dont have to pay for Amazon S3).

I think this is a good and safe enough solution (for me) when it comes to a "real wallet".
Obviously there are still risks and most of them are solved by having a "bank", containing all the bitcoins I can't afford to lose, where the wallet.dat is encrypted in a TrueCrypt container hidden in Wuala, Dropbox, locally on my computer and on a physical medium.