The answer that I started to write is a combination of Gjergji's answer and David's answer. Let $G$ be a countable group which is not a finite union of translates of non-principal square root sets and a finite set. Then as David says, you get infinitely many independent chances to find $p$. As in Joel's original set-up, you can also use biased coin tosses to make the edges.
I'm left wondering when a countably infinite group is a finite union of translates of non-principal square root sets and a finite set. I guess that $C_2^{\infty} \times A$ is an example, if $A$ is a finite group which is not an elementary 2-group. Certainly no elementary $p$-group (or, additively, no vector space over $\mathbb{Z}/p$) is an example, and neither is $\mathbb{Z}^n$. And I guess that $\text{SL}(n,\mathbb{Z})$ isn't an example either.