How can I setup and deploy a database with Deis (PaaS)
If you're trying to deploy now, a possible solution is to set up a docker container, have it publicly route-able, and then configure your application to use that container through an environment variable following Heroku's 12 factor app best practices. There is a feature request for a Deis service gateway that will act like Heroku's Add-on Marketplace, but it's not there yet.