You can click the "try another way" link, which will allow you to use a TOTP code (which they call the "Get a verification code from the Google Authenticator app" option even if you've never used Authenticator).
I don’t have experience with TOTP on this, but I’ve seen that the “try another way” doesn’t even work with a recovery email address and a code sent to it. Google seems to make it almost impossible to login if you move away from your “home” location, unless perhaps you use its apps and are already logged in.
