You say that you want it "random" in some sense. But then your comment indicates that you don't want areas where there are no points. The problem is that at SOME fine-ness, a random sampling will always have holes in it. That is the nature of randomnity (I may have just coined that word.)
If you choose to bin things so that there are some points in one bin, and others in an adjacent bin, then there is a decent chance that the points in both bins 1 and 2, by random chance, may all lie away from the common edge. If you have enough bins, the chance of this happening in SOME bin are actually very good. In that case, you will perceive a hole in the sampling.
This will happen not matter how you do any random sampling. So really, you don't want a random sampling, even though you say you do.
In fact, you probably want some variation of sampling that has all points in some way uniformly distant from their neighbors. I'd suggest the idea of looking for a uniform tiling of a sphere, so maybe this as a starting point.