If you printed out the hardcopy one-time codes like they instruct, you can immediately log in with that as soon as you realize the phone has been lost and remov

If you printed out the hardcopy one-time codes like they instruct, you can immediately log in with that as soon as you realize the phone has been lost and remove the Android device from your account so that it can no longer generate the 2-factor codes. You also can't change your Google Account password from your phone and once you enable 2-factor auth, your Android phone's sync/email/etc uses an application specific password to authenticate so your master password isn't used on the device anymore. You can also kill that application specific password from your web-based profile settings and while it doesn't "wipe" the phone, it halts further syncs.