How do I recover an email address I lost when my phone was stolen?

Tay's mobile was taken and his password changed. How can he get back into his inbox?

Somebody stole my phone and changed my email password. I've tried to recover it, but I don't have the phone number linked to my account because my phone was stolen. What should I do? Tay

First, recover your phone number, which is much more important than the phone.