Have you verified that the probabilistic-primality-test approach is too slow for your application? Miller-Rabin usually requires very few tests for a high level of certainty.
You might also look into libraries that provide primitives you can use. In particular, Java's BigInteger class has such methods built in. You could take a look at the method isProbablePrime(), which takes as input a certainty parameter $a$ and returns a number that is prime with "probability" (or certainty) $1 - 1/2^a$.
I wrote a test program to generate random pseudoprimes using this library (I can post the source if you are interested). The default certainty is $1 - 1/2^{100}$. Generating 100 primes of length 1024 bits takes only 20 seconds on my laptop. On the other end of the scale, generating 100,000 primes of length 40 bits takes only 20 seconds. So if you are interested in an application, it could be worthwhile to use something already available first, then plug in your own solution later if running time is an issue.
Another question (and more relevant to mathoverflow) is what sort of distribution you are looking for. I have no clue how one would go about getting a uniform distribution on primes in an interval with any decent guarantees, unless one lists all primes in the interval first and selects from it uniformly. For selecting very large (e.g. cryptographic) primes, the usual approach is to just generate a random number from the interval uniformly, then test the successive odd numbers after it until a prime is found. Because primes are so dense and the scale is quite large, this should approximate selecting a random prime from an interval quite well asymptotically. But this requires some bounds on the prime gaps, which hold in the large limit, so if you are interested in more mundane intervals (like around $10^{10}$ where it is still infeasible to list all possible primes), I don't know of any good guarantees.
