For Google specifically, you can use:
1) SMS
2) The Google Authenticator app, which doesn't even require the phone to have a WiFi connection (it continually shows a changing code that you enter on the site to log in).
3) Printed codes -- you can print a sheet of 10 one-time codes to use as emergency backup (phone lost, etc). Obviously you have to ensure physical security of that sheet. I might copy 2 or 3 of these into a discreet place in your wallet, and leave the rest someplace secure that someone you know could get for you in a true emergency.