I am still indulging in a bit of Hearthstone. I am not interested enough to invest the money it would take to be competitive, so I have mostly played modes where your card collection matters little or not at all: Tavern Brawl and Dungeon Run. (I could also play Arena, but there is a gold cost there.)
In both modes, I must say that the skill ceiling is a little higher than advertised. I would not say a lot higher, but there is clearly better and worse, and you can see worse decisions being made. Tavern Brawl may tend towards very messy randomness, but understanding how to use that randomness can be the difference between winning and losing. I have won several games I should have lost because my opponent kept rolling the dice after reaching a decisive lead. As in, they could win simply by attacking, but instead they triggered a random effect that wiped the board. This is a skill important in many games (and outside them): recognizing that you have already won and taking your victory.
I have completed something like 30 dungeon runs (better stats forthcoming once the interface is better). I wanted to complete the dungeon at least twice on each class so I was not misled by having a particularly hard or easy run. I have defeated every NPC deck at least once. There is still some streaky randomness, as I completed 3 of my first 4 Druid runs and then 2 more in the next ~70 bosses defeated. I do not think I got that much worse after the first few tries.
I have pretty clearly gotten better at this. I am clearing more dungeon runs now than I could in my first week of playing. I have a better understanding of the card pools available, how they interact, and how they interact with the NPC decks. (It would be really sad for the game if there was no room to grow starting from zero, even for an experienced gamer applying lessons from other games.)
That said, there is still a skill ceiling due to randomness. I doubt I could reach a 50% success rate, although 33% seems feasible. When you stack random card options, random opponents, and random stacks of the deck, there are too many ways for the cards to fall the wrong way in eight games. Some of the cards are that much better, and you will probably win. Some of the opponents are that much harder, and you will probably lose.
For example, I found Warlock runs easiest, once I got the swing of the class. Several of the card pools have giants in them, and there are multiple artifacts that let you get them on the board in the first few turns. In my second Warlock win (final boss), I played three Molten Giants on turn 2 (Scepter of Summoning + dealt myself 5 damage = free giants). In the run before that, Azari the Devourer ate both my artifacts on turn 2 then went on to eat all but 1 of my giants. I lost that one.
“Luck is where preparation meets opportunity.” You can get better at preparing. You can get better at watching for opportunities. You still need the opportunity to arise.