What I think would really increase PvP fun and variability is the introduction of game modes.
Game modes are different types of games (I would say specific to PvP, but could be introduced in PvE with a lot more work).
A few examples:
-You may pick a (small) number of cards from your deck, which you draw first.
-You may pick a (small) number of cards from your deck, which you draw last.
-You may pick a number of cards. These will be somewhere in the first half of your deck.
-You may pick a number of cards. These will be somewhere in the last half of your deck.
-Only a fixed number of upgraded cards allowed.
-Start with 50 hp
-Start with 200 hp
-Start with a triple mark
-Start without a mark
-Random
-User specified card type exclusion
Using game modes will of course drastically change the balancing of certain decks, which is kind of the point. =D
This will require some kind of lobby system, but the game needs that anyway.
Obviously, once the use of options is programmed in, adding variants of these should be very simple. Also, they can be combined with each other, and with tournament rules the way they are defined right now, providing a huge number of new combinations.
This allows for many new and interesting tournaments, and it greatly promotes the making and updating of many different kinds of decks, instead of specializing in just one or two decks.