I find the Gold cost idea strange. If it is implemented, there should only be 3 costs for common, uncommon, and rare cards. Of course, one might desire one card over another from the same rarity due to keyword etc, but each card of the same rarity should be equally valuable when using it at an ideal situation.
Now this doesn't sound too attractive does it?
Furthermore, it's unfair for new players because they won't know which card is more worthwhile of purchasing without ever try the card with their deck.
Here's a more random system:
1. Every player start with the exact same deck/cards, or,
2. Everyone start with a random deck of 45 random cards, in another word, everyone's starting deck is different and can not be modified until you get new cards.
3. Everyone start with more than 45 random cards, say 50 or 60 to allow minor adjustment.
Now, say every 5 victory or 10 loses or whatever works, the system will give you/player a new random card that is not in your card pool. so this way player collect cards at a fix speed.
To make things harder, the system could assign any card to you, therefore it will be harder to receive new cards later. If one is unlucky, he/she might never be able to get the card he/she wants!
This idea works like cards games on the market where you buy booster pack without knowing what card you are getting.
Pros:
battles could be interesting with lots of variety.
every card will probably be used.
Cons:
could be frustrating to get the card one wants.
some victory condition (ex: titan) will be extremely hard