I got into this predicament earlier today and want to save everyone the trouble I went through.

I broke the screen on my old phone. I went to the mobile store and got a new one no problem. But when I tried to login, it kept trying to do 2FA with my old phone with no other option. The poor guy at the store was no help.

After Googling and even calling into Google One, I was told I'd need to "recover my account" by sending documents proving my identity to Google. I told them I didn't need to recover the account, I just needed to login to a new phone. After an hour of texting with the guy I found a workaround.

On your initial sign in with the new phone, make up an entirely new (and temporary) Google account. That will let you go through the main setup.

Then go into Manage Accounts and add back your old Google account and now 2FA can text you properly and you can get through security.

Hope this helps someone else.