This happened to me - I even had access to my recovery mail but google just decided I wasn’t trusted back in my account after I moved to a new country. I contacted every support line I could but alas.
About 3 years later I was magically let back in, no idea why but I would try every few months and it just worked one day. Hope it doesn’t take that long for you.