Make an appointment at the Genius Bar in your local Apple store. Take the phone, photo ID, and proof of purchase for your phone with you (this shows proof of ownership). They'll be able to help you from there.
If you know the old email address, use it to log in to iCloud. From there you can change it to the new email address.
Manage ID https://appleid.apple.com/