Pseudo random, unqiue integer numbers in a given range

Question

I need an algorithm that gives me integer numbers with the following features:

• Numbers must be in a given range $[n..m]$;

• Numbers must be returned in pseudo-random order (random at visual inspection is enough; it is more important that numbers are well distributed over the given range);

• Numbers may not repeat before each number in the range $[n..m]$ has been returned once;

• Range may be huge (up to $2^{64}$; this excludes all list/shuffle based algorithms);

• It should be possible to seed the function so it returns numbers in different order on repetition;

• Algorithm should be as fast as possible and should return in constant time.

I wrote code that uses table based bit swapping and optionally XOR and/or addition. It works very well for bit-aligned $n$ and $m$. However it is a bit slow and if the range $n..m$ is not aligned to bits (i.e., $n$ other than $2^x$ and $m$ other than $2^y$), I get either gaps within the returned numbers or extremely non-constant runtime behavior.

How can this be solved?