Você já tentou executar a migração diretamente do bash dentro do servidor heroku? Se não, tente o seguinte...
heroku run bash --app your_app_name_goes_here
bundle exec rake db:migrate
A primeira linha de código abre o terminal de comando bash e a segunda migra o banco de dados como de costume.
Esta não seria a solução sugerida. Mas, caso você NÃO se importe em perder dados no banco de dados, você pode tentar redefinir o banco de dados primeiro e tentar novamente. Novamente, não faça isso a menos que esteja disposto a perder os dados existentes!
heroku pg:reset DATABASE
heroku run rake db:migrate
No entanto, você pode fazer isso via bash como antes.
Espero que isso ajude você.
