Lazily computing a random permutation of the positive integers

Question

Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)?

What I mean is this:

An algorithm that, given a source of randomness and a positive integer range (for simplicity it could be restricted to starting at 0 and ending at n), can be asked to produce the next value in that range. This can be repeated n times, and a different number is provided by the algorithm each time.

If the caller were to push all of the values retrieved from the algorithm into a queue the resulting ordering would be just as random as if the result had been generated with the Fisher–Yates shuffle.

The naïve implementation would be to pick a random number in the range, check to see if it has already been selected, and choose again if so. This algorithm starts efficient enough, but has increasing complexity for subsequent calls -- too expensive for real-world applications. To really be useful it would have to be O(1) for each trial, though a good logarithmic time might be applicable.

It has to be lazy because with large ranges (such as a 64 bit unsigned integer) it would take Exabytes of storage to precompute the whole permutation, and it is unlikely that a real-world application is going to actually need all of the range; merely it needs that the entire range was considered in values it is actually going to use.

Essentially the problem is just lazily generating a mapping between the integers in a range and a random permutation of those same integers, though being able to access the mapping at arbitrary points instead of just sequentially is but a bonus.