Is there a randomized algorithm for set-cover?
Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover.

input: collection of sets over $n$ elements, upper bound $U$ on opt

output: w/probability $\ge 1/2$, a set cover of size $O(U \ln n)$.


Let $K=\lceil \ln(2n)U/0.99\rceil$.  Let $T=\ln(100)$.
Create $K$ tokens, each with an associated unit-rate Poisson process.
As time $t$ increases continuously from $0$ to $T$, do the following:
When a Poisson process fires at time $t$, 
remove its token from its current set (if any), 
then place it on a set $s$ chosen to maximize
$$
\sum_{e\in s}
\Big(
\frac{1-1/U}{1/f(t) - 1/U}
\Big)^{C^{(t)}_e},
$$
where $C^{(t)}_e$ denotes the number of tokens (other than the firing token) 
currently covering element $e$, and $f(t) \doteq 1-\exp(-(T-t))$.
Return the sets that have tokens on them.


When a token fires, it moves 
to a set whose elements have largest total ``weight''.
Initially, when $t\approx 0$, the weight of element $e$
is about $.99^{C_e} \approx 1$,
so the algorithm essentially moves tokens onto the largest sets.
When $t\approx T-\ln 2$, the weight of an element $e$ is about $.5^{C_e}$.
Thus, each token on a set covering $e$ cuts $e$'s weight by a factor of $1/2$.
Finally, when $t\approx T-\epsilon$, an element $e$ has weight about
$\epsilon^{C_e}$, so only uncovered (or minimally covered) elements contribute significant weight.

If $U$ is unknown, 
then binary search can be used 
to find the smallest integer $U$ 
between $1$ and $n$ 
for which the algorithm works.

Here is the approximation guarantee:

Theorem.
If there exists a fractional set cover of size $U$,
then, with probability at least 1/2,  the algorithm returns
a set cover of size at most $\lceil \ln(2n)U/0.99\rceil$.

For the derivation and proof see https://algnotes.info/on/obliv/greedy/set-cover-grasp/.

One more

Oh, and there is a well-known randomized parallel algorithm for set cover, namely Primal-dual RNC approximation algorithms for set cover and covering integer programs by Rajagopalan and Vazirani.