This is a problem studied in Gravitational Waves (GW) data analysis for example, where you need to sample the surfaces of possible (GW) signals to obtain a finite subset of the signals to compare (see matched-filtering) to the output of your detector.
See for example this paper and references there.
The algorithms for non overlapping "coins" go under the name of "stochastic algorithms" in the GW literature, and they can be show to be more efficient than pure random sampling, but less efficient that regular lattice distributions (only true for the low dimensional case).
The point is that at least in 2 dimension it's possible to start from a stochastic distribution and start moving the "coins" around until they crystallize and reproduce an hexagonal lattice (which is know to be the optimal placement).
The subject is still open because: optimal placement are not know for higher dimensional spaces, the (hyper)-surface my be curved, the metric tensor might be difficult to obtain or difficult to diagonalize... etc.
So in general the problem is still open and the answer will change from case to case, but in 2d for a flat surface given in coordinates where the metric tensor is the identity the problem is basically solved.
Regarding your question in particular the efficiency of your algorithm can be estimated and it's worse then an hexagonal lattice. Since with a Markov chain you can get closer to a lattice the two algorithm have clearly different performances.
Notice that I don't know up to which dimension things have been actually tested.
"Weird" things can happen in higher dimensions: if you allow the coins (hyper-spheres) to overlap the random distribution becomes very efficient, but boundary effects become also determinant.