Your best bet would be to file a support request at:
https://one.ubuntu.com/help/contact/
Use an email address you do control in the form, but give the deleted email address in the message body so your account can be identified. If you've got any ways to prove that you are the person who controlled that email address, that would be helpful too.
Once you are sorted out, consider adding a backup email address to your account. The Ubuntu Single Sign On system lets you register as many email addresses as you want, and this will ensure that you can retain control of your account should one get deleted:
https://login.ubuntu.com/+emails