As per the Heroku support staff, this is the magic thing:

heroku config:add LANG=en_US.UTF-8

Although heroku console will keep reporting strings encoding as ASCII-8BIT, your actuall app will be running with the correct encoding, based on the LANG config var. You can double check that by doing this:

$ heroku run bashRunning bash attached to terminal... up, run.2u20415@022e95bf-3ab6-4291-97b1-741f95e7fbda:/app$ irbirb(main):001:0> "a".encoding=> #