I've gotten as far as adding a button called "Shuffle" to the editor. I have a lot to learn.
I think you're right, combining brushes with a replacement of settings would get really crazy. What about this instead-- an "averaging" of the settings, like a cross-pollination? Almost if two brushes had a baby. So if each brush setting is a set of points defining a curve (for each input), we could average two sets of points to get a new curve. That should avoid extremely jarring changes of brushes and be more likely to result in something you might predict.
For the randomize function, the one thing that worries me is that some settings/inputs have a really wide range of allowed values but in practice only a very narrow range is useful or even function. We'd have to identify new ranges that are "sensible" or even blacklist some settings (Opacity Multiply comes to mind). Or, just deal with the likelihood that most brushes generated by the Shuffle are going to be horribly broken :-P.
Another thought I had is that maybe the randomize function only shuffles a random subset of settings per click. Maybe a total of 10 setting/input combinations. This would mean that with each shuffle the brush becomes more complex, which might affect cpu usage.