Install Shapely with GEOS on heroku
Haven't tried, but found a tweet that looks promising and leads to a repo even more promising.
Seems like the concept of "buildpack" is a way to get things loaded on Heroku, and someone has made GEOS iavailable as a buildpack. By setting a custom geos-path you can install Shapely via pip and it will find GEOS.
Heroku now has built-in, experimental support for a few geo-location libraries including shapely's dependency GEOS.
You just need to set the following config variable from your command line:
heroku config:set BUILD_WITH_GEO_LIBRARIES=1
You can find out more here