[throwaway27727]

For Android, you had better keep your 2FA codes in an accessible location if you plan on locking/finding your phone. There's nothing like losing your phone, trying to log into your account from your SO/friend/stranger's phone so that you can. get to Find My Phone, and being blocked from taking action because you don't have your 2fa codes on you.

Solutions: First obvious one is to keep a physical copy of your recovery keys in your wallet. Of course, that doesn't help if your wallet is stolen, so the next option that I use:

Keep a KeePass (or equivalent) database in a hosted cloud like Dropbox (that DOESN'T require 2fa), holding your recovery keys. This way your database is protected by two passwords, so that if either are compromised you are still protected. You'll have to memorize both passwords but that's a good tradeoff imo. Then use KeeWeb (preferably a self-hosted one) to access your database and codes. So the model here is: borrow a phone, log into Dropbox, download KP database, open KeeWeb, open database, and get your 2fa codes. Log into Google (actually, third password you should memorize), and lock/ring/clear your phone.

[lazyeye]

Buy a 2nd cheap $50 android camera phone, install authenticator but with no sim card or wifi access. Make sure all your authenticator codes are also registered on this phone as a backup.

It is no problem to register the same authenticator code on multiple phones.