herokuサーバー内のbashから直接移行を実行してみましたか？そうでない場合は、次のことを試してください...
heroku run bash --app your_app_name_goes_here
bundle exec rake db:migrate
コードの最初の行はbashコマンドターミナルを開き、2番目のコードは通常どおりデータベースを移行します。
これは推奨される解決策ではありません。ただし、データベース内のデータが失われることを気にしない場合は、最初にデータベースをリセットしてから、再試行することができます。繰り返しますが、既存のデータを失う意思がない限り、これを行わないでください。
heroku pg:reset DATABASE
heroku run rake db:migrate
ただし、これは以前と同じようにbashを介して実行できます。
これがお役に立てば幸いです。