I was the GSuite Admin, trying to log into my GSuite Admin account, and had control of the domain, so this might not work for you.

One of the problems being on the legacy Google Apps for Domains free accounts is that you're not technically entitled to support.

So, this might not work for your situation.

In any case, for me I went and logged a ticket through https://support.google.com/a/contact/recovery_form

You will then get an email to the nominated email address in the form telling you the case is opened. Don't get your hopes up just yet.

A while later you'll get an email telling you that you're not entitled to support because you're on the free plan, and to go through the self reset options (which you already did, presumably via https://accounts.google.com/signin/recovery)

If you reply and explain that you've done this, and you're still getting <the error message specific for you> - it may be assigned to a human. If it's not, try again, maybe with a new case. You will need to be patient - expect 24-48 hours between you sending them email and them responding.

For me, they wanted me to prove domain ownership (TXT records), as well as a whole bunch of information about the account and it's users.

Once I submitted the ownership information it took several more days, and then they send you a one-time reset link to reset the password (yes, even though I knew it).