Tell steam everything you can, they understand situations like these happen and by explaining what happened they could help you.
Stuff you should tell steam:
- The email you used
- Login name
- Last password used
- Last time you could get into the account
- Tell them you no longer have access to your email
When making the steam support account, use an email you can use with steam to as they will most likely set your new contact email to the same one on your support account.