You need to contact Google AdWords support as they seem to handle Analytics issues as well. However you first need to have an AdWords account, so sign up for AdWords (you need not enter any billing information).
You can choose any option on the above page to contact AdWords support, I chose the email option and they replied back with the restore process.
Ideally, you would need to contact the administrator, but in your
case, I understand that you're unable to place them - and for security
reasons, we're unable to disclose administrator information to you.
What I can do to help you is write on your behalf to the current
administrator/s on this Analytics account, requesting them to get in
touch with you.
If you would like me to go ahead and do this, please reply to this
email stating so, as this will be the first step.
In case this doesn't help and we don't hear back from the
administrator (within 7 days from when I write to them), I will share
with you the steps to prove ownership of the domain(s) being tracked
by this account, and thus gain access to the account independently of
I was lucky with the first option itself, but it was good to know that I could recover the account by proving domain ownership too.