I had just had a problem like you described with Google Authenticator, where I got a new phone and I couldn't turn on my old dead phone for its Google 2FA; I was totally locked out of the service until I found a way to briefly get the old phone to start.

Authy would have let me just use my new phone! Here's a trick for those still wanting to use Google Authenticator- when you sign up for a new account, save a screenshot of the QR code; that way I think you'll be able to recover on a different phone if you scan that (just remember to store the QR code safely!).