To try out a feature branch, I pushed it to Heroku's master (since that's the only branch it uses for your website), i.e. I did:
git push heroku feature-foo:master
! [rejected] master -> master (non-fast-forward)
error: failed to push some refs to 'firstname.lastname@example.org:foo-repo.git'
hint: Updates were rejected because the tip of your current branch is behind
hint: its remote counterpart. Merge the remote changes (e.g. 'git pull')
hint: before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.
The answer turns out to be simple. Do a forced push, i.e.
git push -f heroku master