In Magic: the Gathering this balancing act is achieved by a set of constantly changing "environments" (sets of cards) that are updated every few months, when a new set of cards is published. Sets "rotate" in and out of the various environments and there's a few where it's legal to play with all cards ever printed (excluding some that are banned or restricted for being OP- Over Powered).
When a new set rotates (its cards become legal) in a given environment, there will be a reshuffle of the balance of power between already-established decks, that now acquire new cards or lose cards they needed, and some new strategies become available resulting in new decks being designed. Eventually the dust settles and the "tier one" decks (the ones that win the most) are found. Then tournament play in particular becomes a rock-paper-scissors affair, until the next update.
In some of the environments were all cards from all sets are legal (again, minus the ones in the banned or restricted lists) games indeed often come down to a coin toss: the player who goes first wins (in one turn, through some OP combo, typically).
I suspect that a perfectly balanced game is impossible to have and would probably be boring even if it was possible to have it. An element of creativity with constantly updated design parts, like in M:tG is probably the best one can do.