I was thinking about adding some sort of single-player campaign, where you would have to defeat a series of different decks and you would have to modify your deck to counter them, so a "deck building" menu would definitely be there.
This sounds like a great idea. Similar like the Magic MTG 1997 game, where you travel a map, duel enemies and gain their cards to strengthen your deck.