Sounds like a scam to me - please tell me you didn't click on any links in the email
If you use a browser to go to gmail, you could try to use the standard password reset mechanism, though chances are that if your account has been hijacked, they've already diverted your alternative e-mail account.
Alternatively, in the browser go to the main Google site, click the Sign In button then on the next screen, click the Sign Up button and create a new account.
In future, when you get e-mails about security breaches or from banks or anything that involves logging in or security, remember to NEVER click on a link in the e-mail. If you think the warning may be genuine, open a new browser session and manually go to the site and log on.
Just like if someone calls you claiming to be from your bank or a government agency or whatever, you NEVER answer security questions because you don't know they're who they claim they are: you go find the institution's phone number and call them back yourself. Simple common sense.
