Ended up writing something of my own based on UUID.java implementation. Note that I'm not generating a UUID, instead just a random 32 bytes hex string in the most efficient way I could think of.

Implementation

import java.security.SecureRandom;
import java.util.UUID;

public class RandomUtil {
    // Maxim: Copied from UUID implementation :)
    private static volatile SecureRandom numberGenerator = null;
    private static final long MSB = 0x8000000000000000L;

    public static String unique() {
        SecureRandom ng = numberGenerator;
        if (ng == null) {
            numberGenerator = ng = new SecureRandom();
        }

        return Long.toHexString(MSB | ng.nextLong()) + Long.toHexString(MSB | ng.nextLong());
    }       
}

Usage

RandomUtil.unique()

Tests

Some of the inputs I've tested to make sure it's working:

public static void main(String[] args) {
    System.out.println(UUID.randomUUID().toString());
    System.out.println(RandomUtil.unique());

    System.out.println();
    System.out.println(Long.toHexString(0x8000000000000000L |21));
    System.out.println(Long.toBinaryString(0x8000000000000000L |21));
    System.out.println(Long.toHexString(Long.MAX_VALUE + 1));
}