Randomness is a very popular (and good) answer to skill gaps, but it's also a dangerous knob for game designers to turn.
I quite enjoyed the early days of Hearthstone, including the random factors in who won. But successive releases kept adding more randomness, and specifically uncontrollable randomness, until I quit the game. (It may have improved, and this didn't make it a bad game. It just wasn't for me anymore.)
Most people recognize that War is a bad game, because it's entirely random and has no element of choice. But a game like Mario Party is full of choice, and yet the random payouts are so large that skill is often irrelevant. Even near-perfect play can be dominated by random factors, and those random elements (specifically, bonus stars) aren't numerous enough to average out over the course of a game. That's what broke me on Hearthstone: the feeling that the randomness that was too scarce to average out over one session, too potent to avoid or overcome, and too unconstrained to strategize around.
At the far end of that spectrum, a game like poker consists almost entirely of strategizing around randomness, because the random factors are common enough to view statistically and only indirectly produce winners. And so the better poker player will win pretty consistently, and having fun across skill gaps starts to become difficult again. (Hence the popularity of moderate-randomness card games Euchre for social play.)
Randomness is often a good addition to games, especially in combination with hidden information. Not only does it make play across skill gaps worthwhile, it makes them more replayable. But there's a lot to be said for adding it carefully, in places where players can exert some measure of control.