I found that you do not need to do the ReinstallJava[]:

This works and solves the problem:

Needs["JLink`"];

InstallJava[CommandLine -> "/usr/bin/java"];

AddToClassPath["/Users/xxxx/WhereverYouWantThis"];

I know it's silly and bad form to reply to my own post, but minutes after hitting the "Publish" button I found out that all I had to do was to point JLink to the correct location of the java executable. So, with the current versions of JDK 8, this gives:

Needs["JLink`"]; InstallJava[]; ReinstallJava[CommandLine -> "/usr/bin/java"];

and then after that everything works fine for me.