Here is an outline of a fairly efficient way to do this.
Say you want to generate $m$ points with a minimum separation of $d$, in a box of size $s \times s$. Let $d_2=\max(d,\sqrt{m}/s)$. Partition your box into subsquares of size $d_2 \times d_2$; these will be used as bins. We will generate, say, $3m$ random points in the full box. Now place each in its appropriate bin. This can be done in $\mathcal{O}(m)$.
Now iterate over the generated points. For each, locate its bin, and gather all points in neighboring subsquare bins. For each such neighbor, see if it is within distance $d$ of the candidate point and has already been chosen. If not, the candidate point is chosen as a member of our random set, and a down value is set to indicate this (so checking each neighbor is $\mathcal{O}(1)$).
We stop once we have $m$ points collected, or else run out of points. If the latter, generate more, add them to the existing binds, and proceed as before.
The memory hoof-print is $\mathcal{O}(d_2^2)$. The speed will typically be $\mathcal{O}(m)$ unless the sizes of $d$ and $s$ make it either difficult or impossible to have $m$ points inside with minimal separation of distance $d$.