I keep backup codes for each of my 2FA services in a Truecrypt container, which is mirrored on Dropbox. Additionally, I keep a copy printed out and kept in a fire safe. Phone backups for personal accounts have my wife's phone on record, and I try to keep printed copies of the QR codes I used to set up the account.
About a year ago, my phone was shattered while on the road, and while I was able to regain access to those accounts due to existing login sessions on my home computer, I'd have been sunk without them. Make sure you have a plan for what you do if your phone authenticator becomes unavailable.