I tend to play mostly 3-4 player games with the same people. We use Jack of All Dominion as our randomizer. Before each game, each player is allowed to pick 1 or 2 rules, then we hit "shuffle". The rules can be 1,2,3+ cards of a particular type, veto cards (or card type), etc. Basically any of the options.
Sometimes we don't bother to clean out the rules between games. So the first game may have 3+ Adventures cards, 2+ trashers, and no attacks; the second game might then have 3+Adventures, 2+Prosperity, 2+Trashers, 1+Villages, 1+ +Buy, and no attacks. The third has more restrictions. When JoAD gives up, we reset the rules.
When we end up with Black Market, we grab a stack of randomizers from a shuffled pile. We discard in-play kingdom cards in the black market if and when we get to them. Bought black market cards are fished out of storage when bought.