High five for the Borges reference. Anyways, I think you could probably add some simple smarts to the deck randomization that would make it more fun. Like, it starts picking some cards at random, and each new card exerts certain preferences on future choices. For example, if the first card is an undead card, future cards are more likely to have the undead keyword (and certain cards, like death wave, become more likely, and other cards like retribution become less likely). There's still an element of randomness, but you're less likely to end up with really useless decks. It could also keep track of the average recruit/brick/gem cost, and compensate if any one of them was too low by preferring cards that use that resource. I don't know, maybe this would be too complicated.
You could also use a really naive algorithm that just chooses a certain number of keywords, fills up the deck with as many cards with that keyword (and support cards for that keyword), and fills up the rest randomly. That way you wouldn't have to hand-code information, but the results would probably be more hit-and-miss.