Are you certain you cannot get to the 2FA settings?

Under Settings -> Security & Login -> Two Factor Authentication -> Use two factor authentication -> Edit

Then you can add a new app or turn off. Or select an alternative/backup approach.

That is through the web UI. Not tried the phone TBH but I'm assuming you're using the web as you said you reset your phone.

Off topic I appreciate, however, your experience is a reason I moved away from Google for MFA.  I use Bitwarden though you dont have to use that - I would suggest you use something that allows you to backup your db, sync across devices and/or is available online (like Bitwarden).