Earlier quoted context omitted.
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)
You should be using POP or IMAP only on your phone so that you can revoke permission after it is stolen (when you log in to your account from a desktop and use a backup key from the printout). If you are logged in to your main Google account on your phone you are asking for trouble. While I will be sympathetic after it gets stolen and someone ruins your life, I won't be surprised.
They can wreck havoc, but they cannot change your password and steal your account.