I had similar issue - I know the passwords, the recovery email but does not have a phone number associated with it. I can't login. Thankfully, that Google account has no important data.

Only thing you can try is to use the same device and browser and this time, use your mobile internet to access it (if not done already). This might have 1% extra chance of success but there's no guarantee.

Google's AI (or the engineer's brain) has decided that logging in with new routers is only the job of a scammer or a terrorist, hence you're logged out permanently.

I've moved 90% of my life away from Google. Perhaps you can try that as well.