@leocg Hello, this is still me. So, in my desperation I looked into my folder that has a bunch of text files backed up, lo and behold, there was an "Opera backup codes" text file. Popped in the code, and deactivated 2 Factor Verification.
Although, I will say this, with the ease of setting up of 2 Factor Verification, there should be even more precautions taken. Like this whole "You lose the phone, you lose the account lol" system is so silly. Like what's the need of linking an account then, how is it different from just "Device 2 Step Verification". Very dumb system. Just a glorified/bluetooth "Device verification". If I had formatted my laptop, instead, or somehow had my data wiped (Without having backed up those codes) I would've been completely locked out. I got lucky this time.
But none of this is even remotely your fault, just wanted to put it out there.
Have a nice day,
and thanks for the help.
P.S. Google never even bothered to warn me about backing up my account in the Authenticator app. Or had done it automatically, either.