Note that this is probably a bad idea because interlacing makes it quite a bit more difficult to usefully compress data.
Anyway, with a (n,m) resolution image, there are n*m points. For each one, you can apply a certain transformation in O(1) time to generate a precise mapping to another point (the specific algorithm is to be thought of later by someone less dumb than I, using XOR with a random seed works for powers of two). Then just send the stream and it works. Theoretically almost randomly distributed* (probably not though, sadly, unless that algorithm is good), and then progresive blah blah will work.