Use a trivial $n$-bit counter, and encrypt it using a block cipher in any configuration other than ECB or CTR, starting with the least-significant bits as your first block so the small change propagates to all the other bits of the result.
If $n$ is not divisible by the size of your block cipher then you'll need to treat the remainder using format-preserving encryption, because the output must be the same size as the input.
This gives you your new index.
If you have the means to decrypt the counter then you can trivially prove that this sequence visits every value exactly once: if any two input states mapped to the same output then you would not be able to decrypt the counter and the encryption itself would be demonstrably broken.
One caveat is that if you jump ahead in the sequence by, eg., $2^{256}$ (presumed to be a multiple of your block cipher size), then the first $2^{256}$ bits of the encrypted count would not change. If you're not happy with this then reverse the order of the bits and encrypt it a second time. Still O(n), but a little more complicated.
Obviously cryptographic primitives aren't a great way to speed things up, but it shows how to make things linear. If you take that construction but replace the block cipher with something more economical (eg., a 64-bit perfect hash) then you can recover a lot of that lost performance.