I've got this working now, and a publicly available version of a custom Heroku Ruby buildpack with pdftk is here: https://github.com/millie/heroku-buildpack-ruby-pdftk
Be sure to see the instructions in the README.
Precompiled version of pdftk for Heroku's Cedar stack is available here: https://github.com/millie/pdftk-source
Hope this saves someone else some trouble!