You don't have to actually enter your email address, you just have to prove that you know it - and telephones have the full alphanumeric set of characters on the keypad. Use a * or # for special characters, and something like "pavel@lishin.org" could be entered as "72835#547446#674".
Edit: I guess that may not be sufficient to identify you, but it could verify that you are the account holder for other services.