> Can you show that [generating a number of records to skip instead of a yes/no for each record] will still maintain a uniform probability distribution?

That should work if you pull the skip count from the appropriate distribution (negative binomial, I think).