I got a similar problem today when I got a new phone, because the old one crashed, and never came back from oblivion. On my new phone I installed the Authenticator app, but to login to that I have to confirm using the Authenticator app, which I no longer have access to on the old phone. There are NO other options for login. Just Authenticator, not email, not SMS, not anything..
This is just ****.. and yes I should have backed up the old one to the cloud, but I didn't know that was an option before now..
I'm having this exact same problem. Very frustrating when it asks for a code on the authenticator app when you're quite literally on the authenticator app! Any solutions? I'm desperate!