Happened to me, I was able to get SMS and recovery codes, but Google still required additional verification on now lost phone :D. On the end I acutely found the phone and was able to restore access. So what they do after couple of days of failed attempts the require additional verification, lets call it 3 step.

I have passkeys, authenticator etc... and everything except phone number, and now i am unable to login my account in other device.

Google sucks, they are randomly denying access because their dumb model can't figure out not everyone is trying to steal account.

This feels objectively worse than writing down a password somewhere