First, cyber security assumptions, which actually make the whole thing somewhat easier to wrap your head around: if you can log into my Google account, game over (or rather, the "game" of recovering from identity theft begins). You can recover passwords to lots of other stuff by asking them to email it to you. So I can reduce the security of a lot of other things to "as secure as my google account." This is simple, and if I have to trust one company not to get hacked, Google is as good as any.
So, let's look at possible scenarios:
Google password stolen (somehow): I just took the plunge and enabled 2-factor authentication. So you'd have to have my password and my phone to log into any of my stuff.
Google password forgotten: I don't think I've ever done this. But I could go through the forgot-your-Google-password rigamarole and eventually get back in.
Google auth token stolen, i.e. someone logs in as me somehow: that is bad. But they still don't have my password, so it's only a one-time disaster- they can't lock me out or anything, and if I see it happening, I can log them out.
Phone stolen: I've got a PIN lock on it. Sure, you could break that eventually. So I've installed "Android Lost" on it to remote-wipe it as soon as I get back to a computer. (it's developed by some guy, and I'm a little leery of trusting so much to just-some-guy. You log in with your Google account, via oauth?, so I don't think even the app maker can access it. The site's not https, which I think is a bad thing: it means some guy snooping your packets could log in to the site as you and run any of the commands. Most of the time this isn't disastrous; all info is sent to your email. But it's on his radar, and I'll not use the site much anyway.
Anyway, Android ought to come with a remote-wipe service; it does if you have Google Apps for your business, but not for consumers.)
Phone lost: Android Lost will take care of that much-nicer situation. I can send a message to the phone, get GPS coordinates of it, etc., so I'll find it somewhere.
Passport lost/stolen: welp, next week is embassy week! Nothing to be done here. I've got copies of it and all my visas online, which might help, but it's not like I can just print myself a new passport.
Incidentally, I just sewed a new pocket inside my pants.
Computer lost: It's got a password lock on the screen, so it'll be a brick to whoever finds it.
Computer stolen: that, plus the hard disk is encrypted.
Wallet lost/stolen: I've got an "emergency card" with my passport. It's got contact numbers so I can call my banks and cancel my credit cards. It's also got Google Authenticator codes so I can log into my Google account even without my phone.
All my belongings are taken from me and I'm teleported into an unfamiliar place, much like the Terminator: As soon as I get online, I can call my parents to help me get an access code so I can log into my Google account (backup phone number). Then I can get all my credit card phone numbers, embassy phone numbers, etc, and start fixing things. Then I'll beat up some dudes and steal their clothes.
Moral of the story: the cloud is wonderful, and security is hard. So now! What bizarre recovery scenario have I missed, and what obvious security hole have I left open?