I had to deal with this a while back because TFA was enabled on my account and I got a new phone and number at the same time so my login options were all broken, and the recovery flow didn't work for the same reasons. Thankfully this was a Google for Work account so there was a way for me to prove domain ownership and they restored my access. If this had been my personal Gmail account (not attached to the domain), I would have had no way to recover it, partly because I couldn't prove ownership so easily, but mostly because they have basically no support for personal accounts.