What about...
Counter-measure
(I feel it's a little complicated, but I'll try to explain what's in my head right now).
Players 1 & 2 fight. Player one chooses a deck and reveals it to player two, who then designs a counter to it. After the match takes place, player two reveals his deck to player one, who proceeds to design a counter to it. The process continues until one player loses twice in a row (fights are played to sudden death), and the winner advances to next round (bracket system) or wins X points depending on performance (swiss system).
This would encourage counter-designing (people would learn deckbuilding as they play, which would be good also for War), with a fun twist: decks can't be too focused or they would be easy to counter as well.
The idea is in a "rough sketch stage" right now. I have some more ideas about it, and I'll develop it if you think it is worthy.