Myth: Right, but what happens in the very common scenario of my Android phone-- logged into Google with the Authenticator installed-- getting lost / stolen? Surely then 2-factor auth is basically useless?
(insert your answer below)
(insert your answer below)
I would also recommend putting an unlock pattern on your phone to protect in case your phone is stolen.
1) You still need to enter your password every time you log in.
2) You can add backup phones that can be called/texted with the verification codes
3) You can print out back-up codes that will always work (once)
4) If your phone is stolen and is using an application-specific password, you can revoke that password for that application.
If your phone gets stolen and it's logged in to your google mail without a lockscreen pin/code, then yeah - the thief can read your mail, 2fa won't help. They can also run your Authenticator app and see the current 6 digit number, but that's not useful without the password as well.
(I'm not sure how easy it is to extract the Google password from an Android or i phone - I wonder if you can just switch them to non-TLS POP3 or IMAP and have them send a cleartext password over an unencrypted wifi connection?)
However, I think google services use XMPP if I'm not mistaken. In which case the password is never actually transmitted over the air. XMPP uses Digest access authentication[1]. Short version: the server would first send a challenge to the client. The client hashes the challenge with a hash of the password and returns the result. The server performs the same operation and compares. So even with a MITM you'd get nothing. Furthermore, the client itself would never need to store the password either.
[1] http://en.wikipedia.org/wiki/Digest_access_authentication
They can wreck havoc, but they cannot change your password and steal your account.