Indexing a random permutation
You can build a block cipher with any desired block size, using a method called "format preserving encryption".  The block size doesn't have to be limited to 64 bits or 128 bits.  This will provide a reasonable solution to your problem.

See Bijective algorithm(s) that can shuffle a range of numbers back and forth, Pseudo random, unqiue integer numbers in a given range, Invertible function that randomizes order, Efficiently generating a uniformly random list of unique integers in a range, Lazily computing a random permutation of the positive integers.