Sem a informação do serviço de e-mail não pode ajudar muito, a não ser indicar o procedimento comum a todos os programas com senha: entra na página de login e clique em Esqueci a senha e siga as instruções exibidas na tela.
OBS: a perda do celular não pode ser problema para redefinir a senha de um serviço de e-mail, se você tinha cadastrado também um e-mail alternativo, que é sempre o recomendado. Não tendo feito isso, a conta provavelmente estará definitivamente perdida. Como o serviço pode enviar o código ou link para o procedimento sem conhecer os dados? Você entendeu? O serviço vai enviar o código para o número que você não tem mais, e sem e-mail alternativo ele não tem como enviar um link de redefinição de senha.