If you are responsible for instantiating a java.util.Random object, then you can subclass java.util.Random and instantiate your own class instead. If some other code, that you cannot change, is responsible for the instantiation, then you obviously cannot use your own subclass. I expect this is not an option in your case.
Another alternative is to change the implementation at class load time. Basically you rewrite the bytecode of java.util.Random to do something else than what it does by default. The downside of this is that it will affect all instances of java.util.Random, not just the one instance that you might want to change. Then again, most code do not rely on the implementation details of the RNG so this probably isn't an issue.
Javassist is quite a nice byte code library. It'll allow you to rewrite byte code at class load time, so you could, e.g. replace the body of the method that produces the random number with a call to your own class that implements the RNG algorithm that you need.
You could write a simple class file processor that will be run for the java.util.Random class. The code might be something like this:
ClassPool pool = ClassPool.getDefault();
CtClass cc = pool.get("Random"); // maybe java.util.Random
CtMethod m = cc.getDeclaredMethod("nextLong");
m.setBody("my.super.duper.RandomClass.nextLong()");
cc.writeFile();