Call Apple
When all the 'normal' (http://support.apple.com/kb/HT5787) verifications do not work, how can the iCloud be certain it is you?
You can call/contact Apple (http://support.apple.com/kb/HT5699). They will try to validate your account by multiple other ways. (billing information, creditcard info, etc). And one of the things they will probably ask for is some email conversations with other persons. So you might need to contact some friends/family/colleagues to dig in there archive for email conversations with your iCloud account.
You might expect your Apple contact to be suspicious, as they have recently had troubles with 'hacked' (wiki link) iCloud accounts.
Might this be a good lesson to always have a valid backup email address and a working 2-step verification☝️.