Email Address No Longer In Service

Hello,
I recently changed service providers and the old service provider has deleted my email address before I could change it. So now I go to change the email on my account but it has to send verification to the old address (which is no longer valid). How can I update my email address to the new one without the old one being in service?
Thank You