Google 2 factor authentication needs 3 things: your Google username, your password, and the token number generated by the authentication application. Stealing your phone gets one of those things.
Or, what if my iCloud gets hacked and my iPhone is remotely erased, can I still access my Gmail and Facebook enough to remove my phone from them?
You get 10 single-use codes to print out for this situation. You can revoke these code and generate new ones whenever and as often as you like.
Your concerns were all similar to what I had. Another was that I have programs that need programatic access to my Google account and I don't want to rewrite them to use 2-factor authentication. That is solved by generating a revokable application specific password.
I found that turning it on and trying it out answered a lot of concerns I had.
How many recovery codes can you print out, and how many can you use? My cell provider (Avea, in Turkey) doesn't seem to pass automated SMS messages on, which has stopped me from using two-factor.
lolwut. and you still keep on using their services? Dude, get to Turkcell or Vodafone and use two-factor if you value your data.
edit:
downgrade if you want to but it will be the day of my death when I let a provider dictate my needs and wants with its stupid rules and regulations. I pay for their services and barring unreasonable ones they have to provide what I need. And passing automated smsses are something that is not unreasonable.
Google Authenticator is available for iOS, Android and BlackBerry, and there are compatible third-party implementations for Windows Phone 7, Windows Mobile, J2ME, PalmOS and webOS. Just search for OATH - it's the open algorithm that Google Authenticator implements.
I don't have a Turkish bank, so I can't speak to that, and every time I have needed it was an out of country issue.
And not having the bank because I'm still waiting for a residence permit, which means I'm still doing the kontor thing rather than having a plan, something that's much cheaper with AVEA.
After that I turned on 2FA for gmail and facebook.
Sure, it's not perfect - but no security is. But is is definitely better than using passwords alone.