Had to chime in here because I've solved this exact problem in the past.
Your first thought was probably to generate pixels by using something like "red with probability p (and thus white with probability 1-p)". But then you realize pixels might be too close together -- this is a *constraint* -- red pixels cannot be too close together.
So what you could do is generate red pixels, then destroy ones that cause the constraint to be violated. This is harder than it sounds when working with an infinite procedurally generated world, as I think you're asking (although this isn't entirely clear from the post).
You want to display what the player can see. But it's not obvious how to make a "generate-and-destroy" type algorithm work, because you don't know that one of the pixels the player *can* see won't later be destroyed because it involves a constraint of a pixel the player *can't* see. An even worse problem is that, depending on how destroy() is implemented, you might never be able to fix it by generating just a little more than the player can see, because there might be "chain reactions" that propagate over long distances. E.g. if A and B are really close, maybe A normally causes B to be destroyed -- but if there's a further pixel C that would cause A to be destroyed when a different viewport is rendered, maybe B sometimes survives, depending on the viewport! And maybe there's a further pixel D that affects whether C is destroyed, and so on, allowing arbitrarily long chain reactions!
The generate-and-destroy idea can be made to work; you just have to be a little careful about it. Divide your map into chunks (I suggest a grid of square power-of-two chunks). Our goal is to design a function create() that builds all the red pixels in a chunk.
First, implement a function called generate() which takes a chunk address and picks a rough set of pixels inside the chunk, which I'll call "green pixels." Green pixels do not obey the distance constraint, and will not be displayed in the final result; they are for intermediate computation only. So for example you can just use the chunk address as a random number generator seed to pick green pixels in generate(). To reiterate, green pixels may collide with each other or with pixels in other chunks.
Higher-level game code asks create() for a chunk at a given chunk address, call this the "requested chunk." create() begins by calling generate() to get the green pixels inside the requested chunk and all neaby [1] chunks. Then create() colors all the green pixels in the requested chunk red, leaving the nearby chunks green. Then create() checks the red pixels one by one for collisions, deleting any red pixel which collides with either a green pixel or another red pixel; this is the "destroy" phase. Then create() returns the remaining set of red pixels.
NB multiple calls to create() are independent. So if your chunks are 16x16 and addressed by upper-left corner, create(5, 1) might be the chunk with upper-left corner at (80, 16). When calling create(6, 1) to generate the next adjacent chunk to the east with upper-left corner (96, 16), that create() call will ignore the red pixels computed at (5, 1) and use the green pixels instead. This guarantees that (6, 1) will return the same result regardless of what values were computed for the red pixels in (5, 1). In other words (6, 1) depends only on the *green* pixels of (5, 1). The red pixels for a chunk other than the one currently being worked on by create() are simply irrelevant to what create() does.
In the grand open source tradition of helping best those who help themselves, I'm leaving plenty for the requester and others in this thread to do. Like writing working code. Or a more complete explanation of why this algorithm can produce neither chain reactions nor between-chunk collisions. Or how this algorithm might work with a vector world rather than a raster world. Or a purely algebraic workout of what's going on here with no appeal to physical intuitions (hint: think triangle inequality).
I highly recommend implementing some sort of caching of generate() results. And I also recommend modifying generate() to include a post-process phase where you remove within-chunk collisions, then removing red-on-red collision check from create().
[1] Close enough to affect pixels in the chunk passed to create() -- this is simply all adjacent chunks if the chunk size is greater than your no-collisions-allowed radius of 8.
