I also had the issue with the FATAL: no pg_hba.conf entry for host error message.
I solved the connection issue to my Heroku Postgres database by adding the following to my JDBC string: &ssl=true&sslfactory=org.postgresql.ssl.NonValidatingFactory.
Example
jdbc:postgresql://host:port/database?user=username&password=secret&ssl=true&sslfactory=org.postgresql.ssl.NonValidatingFactory
You will need the SSL option only if SSL is enabled for your Postgres database (which is the default).
Hint
If you want to check your database connection properties, then just run the following command with the Heroku Toolbelt: heroku pg:info --app your-heroko-appname (make sure that you have Postgres insalled to run this command in your terminal)
The pg:info command will also tell you that sslmode is set to require.
To test the database connection I recommend SQL Power Architect as it is the tool which I was using to check my solution.