I've actually been interested in the topic of random number generators ever since we started talking about doing procedural generation and have been doing a bit of research on the topic. It seems to me as though the class of pseudo-random number generators that are the fastest, and thus most useful for games, are something called XORshift generators, which at their core function through the use of the exclusive-or bitwise operation(not surprisingly).
I wish I could say I understood the mathematics behind it better so as to give a better explanation, but this class of generators depends upon a number of bits of state (in the form of one or more 64 bit integer values in this particular implementation), and as long as all of these individual values are nonzero, the generator should be non-repeating over a maximum interval of 2^(bits of state)-1, I guess depending upon the initial seed values. Take this explanation with a grain of salt, as I'm quite sure I don't really understand it. Anyway, the really cool thing is that working examples of these generators are available in the public domain thanks to a fellow named Sebastiano Vigna, who's website I stumbled upon (thank you Google). I'm still trying to understand his paper, but I thought I might share his website with everyone in light of this topic:
The XORshift page:
I don't know if as they are they are suitable for use in a game as-is, but just by virtue of their completion time being on the order of single-digit nanoseconds I think it's something to take a look at and work on moving forward. In addition, as a way to pay forward the kindness he is doing everyone by making these available to the public domain, it wouldn't be the worst thing in the world to try to find an implementation that passes a more extensive battery of tests than the ones currently implemented and make him aware of it if we do.
EDIT:whoops, said not-or instead of exclusive-or