I know this is a much more 'techie' type of solution, but for an alternative to your methods, have a look at this:

Linear Feedback Shift Registers

LFSRs are basically very simple, very fast pseudo-random number generators that generate a set of unique, non-repeating (but cyclic) numbers.

This is possibly not a solution for implementing in T-SQL, but if you're able to use C# (or maybe even C++) assemblies, it might just work for you.

Alex.