This article has a fairly detailed list of the thing(s) you need to do. I have quoted some of the process below:
Additional Recovery Information
Doing a password reset is the easiest way to regain access to an
account. But it can fail if you forgot your secret question, if the
recover e-mail address is no longer valid, or it the account was
compromised and that information changed.
The Account Recovery Form is the alternative method. It is important
that you complete as much of the form as possible, and that the
information be as accurate as you can make it. If the form is
rejected you can try submitting it again. You can re-submit it as
many times as you want, but always wait for a reply to each submission
before submitting again. If you don't receive a reply, check your
spam/junk folder (especially if it's a non-Gmail account).
It's very important that as you repeatedly submit the Account Recovery
Form that you fill in more of the blanks with more accurate
information. There is some threshold of correct information you need
to prove ownership, so a rejection means you need to supply more.
Submitting the same form with no additional information multiple times
does not help.
While this system works for many people, there are some cases where it
can be very frustrating. But don't give up. There's nothing you can
do (like deleting the account) until you re-gain access to it and
since Google does not offer live one on one support for the free Gmail
product directly these are your options.
Also realize that the more complicated account recover process (that
very few people need to use) is one of the trade-offs for not being
forced to provide a lot of personal information when you create the
account (that everyone has to do). Many people prefer this for
privacy reasons.
Hints for successful account recovery It's not about the number of
times you submit the Account Recovery Form, it's about providing more
and better answers with each attempt. If your submission is rejected,
you must work harder to provide more answers, and make the answers
more accurate in subsequent submissions. Wait for a response before
each new submission (be sure to check Spam). Responses could be
delayed as much as 24 hours but you should wait a full 48 hours before
submitting another form. If you are not receiving a response, check
your Spam or Junk folder on the account you specified for replies.
Also double (triple) check that you correctly spelled the e-mail
account name. Duplicate submissions, or submissions without waiting
for a reply can trigger a submission lock forcing you to wait a few
days to try again. Make your best guess on every field of the form.
You never know what will help.
There may be one other option for simple password recovery if your
account wasn't compromised and you simply forgot your password. If
you have your browser setup to remember your account information you
may be able to view your saved password. In Firefox, you can use:
Tools->Options, Security, Saved Password, Show Passwords. If you use
another browser, then (install and) open Firefox, use File->Import to
import your settings and then check to see if the saved password is
accessible. Again, this only works for people who forgot their
password due to relying on the browser's auto-fill function, but if it
applies it might be an easier than the above procedures.