|Keep It Simple, Stupid|
There are a number of well-documented Pseudo Random Number Generation algorithms available for the searching on the 'net. Each has strengths and weaknesses, and all will produce pseudo-random numbers (even Perl's rand produces pseudo-random numbers).
There are varying qualities of pseudo-random number generators; some are adequate for general purpose use (Perl's rand, for example). Some are suitable for Monte Carlo simulations (Mersenne Twister, for example), and some are suitable for cryptographic purposes (A block cypher in counter mode, or ISAAC, for example).
All of these need to be seeded somehow. Perl's built-in PRNG seeds using a combination of time, process ID, and some bit twiddling, if I'm not mistaken. Porting one of the well-known algorithms to Perl is only half the problem (and in the case of many of the common algorithms, one that's already been solved on CPAN). The other half of the problem is seeding. Perl's method of seeding is again adequate for "general purpose" use. But for more stringent uses, there are more robust techniques; reading from /dev/urandom (non-blocking), or /dev/random (blocking), or through Windows API calls (Windows XP or newer). Seeding in a way that is portable across a bunch of systems is best handled through a module like Dana Jacobsen's Crypt::Random::Seed, which abstracts away the platform specifics, allowing it to be portably useful. On systems where no "standard" entropy pool is available, degrades gracefully to Crypt::Random::TESHA2 (short for Timer Entropy => SHA2).
So to summarize, if I were to write a random number generator that avoided rand, I would first ask what it will be used for. Then I will evaluate the many well-known PRNG algorithms to determine which one meets those needs. After porting its code to Perl (or better, after finding it on CPAN), I would then go looking at how strong of a seed I need, and would probably end up using Dana's module regardless, since it's so convenient and provides options for non-blocking sources.
Finally, I would use tests such as FIPS140-2 to evaluate the quality of the randomness. Of course there are as many types of randomness tests as there are types of PRNGs, so you have to pick ones that test for your use case (ie, statistical use might test differently than crypto use).
The last thing I would do, however, is try to invent my own PRNG algorithm. There's at least 40 years of prior art available to learn from.