Turns out that the particular Gradle binary I downloaded from the Ubuntu 13.10 repository itself tries to export JAVA_HOME. Thanks to Lucas for suggesting this.
/usr/bin/gradle
line 70:
export JAVA_HOME=/usr/lib/jvm/default-java
Commenting this line out solves the problem, and Gradle finds the correct path to the Java binary.
If you just download the binary from their website it does not have this problem, It's an issue with the Ubuntu repo version. There also seem to be some other issues with 13.10 version.