By having the structure you're asking for, along with a sequence, doesn't that make it no longer random?

I've done something similar on a smaller scale to get every 3 character alphanumeric permutation using cross joins. That was pretty quick, but as you want it as a primary key rather than some sort of lookup table you wouldn't want to be dragging around some huge table with every combination