メアドを変えてパスワードを忘れてしまいました・・・

何処のサービスの何のアカウントがという話がわからないので、一般的な話しかできないのですが。

パスワードリマインダー利用（パスワード再発行手続き）に必ず登録メールアドレスが必要な場合は、同じメールアドレスを再度取得し直すのがいちばん手っとり早いでしょうね。

同じアドレスの再取得が難しい（覚えてない、他の人に取られれているetc..)の場合は、
運営元に連絡し、本人確認情報（氏名、住所他）を提示して、アカウントを引き継がせてもらう交渉をするしかないと思います。

当然、本人確認情報を登録していないサービスだとお手上げになるとおもいます。