My ISP recently changed the range of IPs they assign to customers which triggered gmails "hacker alarm" or something and prevents me from logging in. The recovery options they provide (recovery mail or phone via text) don't work either as after trying those it simply says "Sorry, we can't verify its you". Is there any way to bypass this ridiculously broken system? I found this question but the provided link doesn't seem to work (Gmail account hack prevention and recovery)
I would suggest you try using a device in which you are already authenticated. Such as a phone which is using your 3/4G network for example. Once accessing the Google account area you should be able to configure your security settings from their (i.e. correctly update your multi-factor authentication options)
Might be worth once access is gained taking a copy of the printable one time use access codes they offer. They are ideal for situations like the one you have.
I have not tried these instructions, but searching for a copy of the info at the link which OP said no longer worked, brought me to this page:
which at least looks current as of two months ago.
Good luck. Hope it helps.