It sounds like you want a pseudo-random space filling curve (for example, see Context-based Space Filling Curves -EUROGRAPHICS ’2000 (PDF format, 1.1 MB))
Take a look a Space-filling curve.
I suspect you could apply some randomness to the construction of one of these to achieve what you want.