How to migrate accounts to new Google Authenticator app?
This is actually what you have to use backup codes for.
If you can still access your old device and it's rooted you can backup the database and restore it on your new phone.

However, if you can no longer access your old phone and you do not have recovery codes you have to contact their support and sort it out with them.

This is the purpose of two-factor authentication, if the second factor is inaccessible you can no longer access your account. If someone knows your password they can't do anything without your phone aswell.

This is also why services like authy are really sketchy due to the second factor not being offline-only.