I use my phone to authenticate to Google all the time and I have a custom ROM installed. Google doesn’t care. It’s a problem if you’ve installed a custom ROM and messed up flashing GApps, but that’s not on Google.

However, if I read this post correctly, OP didn’t intend to log into their Android device for long. Google’s locked bootloader requires an account login before it’ll unlock, so OP logged in. Then OP installed a custom ROM, which wiped their device (a security measure that happens after unlocking the bootloader).

Google didn’t know the phone was wiped. It still tried to send a login notification to the phone that had only been authenticated once to get Google’s software off of it.

Google also doesn’t always show all verification options, which sucks ass if you’re in a situation like OP’s. Sometimes they’ll accept SMS, sometimes they don’t. If they think your login is suspicious enough, SMS won’t cut it.

Recovery codes are also risky. Recovery codes work (you have 10 of them) but if Google doesn’t trust your login, they’ll require reauthentication on every single screen, including the screen that’ll let you configure your TOTP settings. I’ve seen screenshots of at least one Google user whose connection was flagged to death after a broken phone, and who ran out of usable recovery codes while desperately trying to add their new phone as a 2FA device (or turn it off completely). Google’s flows are broken in those cases, because reauthentication won’t continue the process of changing your settings, it’ll just bring you back to your settings.

The system is intended to work something like this: based on your account history, your session is given a security score. Authenticating with secure 2FA adds points to that score. Certain settings and actions require a certain security score. That’s why you sometimes need to enter your password again despite having logged in already: to raise your score a little.

If Google rates your security score low enough, you’ll need more reauthentication than recovery codes can provide. Their engineers probably flagged changing your 2FA settings as high risk (as they should) but the scoring mechanism can leave you unable to gain enough security points to do any high risk actions.

Yubikey or another FIDO compatible device is the easy answer: unlimited codes that will let you beat the login loop eventually. Very few people used those, though, and even fewer have two (one for logging in, one in a safe somewhere in case you lose your key).

All of this wouldn’t be a huge problem if Google just had competent customer support. In all honesty, their security system is state of the art and easily beats banks and government portals. They just lack the human touch to correct human error.