Lazily computing a random permutation of the positive integers
Yes.  Use a block cipher with a small block size.  This is extremely efficient and requires extremely little state.

A block cipher is a map $E : K \times X \to X$ such that, for every $k \in K$, $E(k,\cdot)$ is a permutation on $X$ (a bijective function $X\to X$).  Moreover, if $k$ is chosen uniformly at random, then $E(k,\cdot)$ acts in a way that is computationally indistinguishable from a function chosen uniformly at random from all permutations on $X$.

Thus, a simple solution is to let $X$ be the set of possible values of an unsigned integer, e.g., $X=\{0,1,2,\dots,2^{64}-1\}$, let $x$ denote a counter ($x \in X$) and $k$ a random key.  The state of your pseudorandom generator is $x$ and $k$.  When you want a new random number, you output $E(k,x)$ and then increment $x$.  This requires very little memory, is extremely efficient, and is provably good (if the block cipher is secure, which is a reasonable assumption given the state of modern cryptography).

You can find information on how to build a block cipher with a small block size here:


Format Preserving Encryption (on Wikipedia)
Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize? (on crypto.SE)
Is it possible to generate a secure permutation F over 32-bit integers even if F(0) … F(n) is public knowledge? (on crypto.SE)
Can I create a fixed length output from a fixed length input? (on crypto.SE)