Без гуглежки побыстрому накатал вот это: 
public static String generateRandomString(){
        byte[] bb = new byte[32];
        new SecureRandom().nextBytes(bb);
        return new BigInteger(1, bb).toString(36);
}
Работает правильно, но валик так не думает. Этой скотине обязательно нужно использование конструктора BigInteger(int numBits, Random rnd)?