So, for a single coin flip and Victory Star, you've got a 75% chance of getting at least one heads (the possibilities are: 2 tails, one heads on first flip, one heads on second flip, or two heads = 3/4 possibilities of getting at least one heads).
I don't think that's any less luck based than the rest of the TCG tbh, the best decks make things as consistent as possible, and 75% is not bad. For instance, an opening hand with either a Sycamore or an Ultra Ball (for Shaymin-EX) I believe is roughly the same–unless I really botched that math, which I wouldn't put past myself.
...anyway TL;DR it's just putting chance in a different place, not really making the game all that much more luck based.