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.
There are two different kinds of directed graphs, graphs with and without 2-cycles. The question posed considers the kind without 2-cycles, but I don't see a problem defining either kind of Rado graph on the same class of groups. For that matter, you could have various kinds of colored Rado graphs, where some of the edge colors are directed and others are undirected. (So, allowing 2-cycles amounts to having two undirected colors and one directed color.)
I don't think that it really says a whole lot about the group. It says that the Rado graph has such a huge automorphism group that many groups act freely transitively on it. It looks like the Cameron-Johnson condition on the group $G$ is actually not only sufficient for a freely transitive action, but also necessary, at least to obtain the $n$-colored Rado graph for every finite $n$ as a Cayley graph of $G$. Still, the groups $G$ that are impossible are essentially impossible for a local reason.
As for the uncountable analogues of the random graph, I might guess that the same constructions still work sometimes, but I would ask someone like Joel Hamkins. :-)