Change Apple ID primary email address
For obvious security reasons, in order to change one's account Email, you need access to that account in the first place. If you don't have access to the email in question (and you can't login) then you are pretty much out of luck. The verification email will go to the new email address to confirm it. 

In the past few days, Apple added a Google-like mechanism to allow you to access your account in the event of a problem with the primary email. Essentially it allows you to answer three security questions. If you don't or can't access those, then a backup email is provided (and verified) so they can help you recover your account. 

But… these things must be done before you lose access.