I have two ideas for gameplay that could potentially be innovative. No promises, but answer with what you think!
Formal Archetypes
We could formazlie the typical archetypes of a trading card game. So instead of Heroes or Classes, you formalize things such as Aggro, Control, Minions, Spell, or whatever other archetypes are typically found in TCGs. There would be sets of cards that are only useable by certain archetypes in addition to the common pool of cards.
What is interesting about this idea for me is that it takes the idea of the metagame and turns it on its head a bit. Rather than the players finding maximum combo decks in the usual way, they are told up front the different types of decks that they can make, and will be making a variant of one of them. The idea would have to be fleshed out a bit, and playtested to see if it was fun.
Choose Starting Hands
The origin of this idea is to replicate some of the functionality of classes without actually having them. Players would be able to choose 3 or so cards that they will always draw first for a particular deck. Because these abilities would appear in every single match with that deck, this would simulate the way that different classes interact with each other.
Possibly these cards could be divided into sets such that some sets require that you take all 3 cards, or some cards are incompatible with other cards when choosing them for the starting cards of a deck.
One thing that I really love about this idea is that it removes some of the huge luck swings that come about with drawing starting cards randomly and needing to mulligan cards. Instead the players have control over how the start of the game will go. Additionally, the fact that there would be lots of starting card combos might allow for more variety than preset classes.
One downside of this idea would be balancing the starting cards. We would not want a situation where all players always choose the same 3 cards, or certain sets of cards are so powerful that they are used all of the time. I think it is at least possible to balance this so that it is fun, though. It's almost like a deck-within-a-deck thing.