Just a video of some work in progress. With this one, you select a face and then run the plugin. In this video, I have it assigned to a shortcut key.
The plugin draws a single line to divide a face, and works on all selected faces. The location of the line is determined by a random number in a user-specified range. A range of 20-80 means the line will be drawn at least 20% from the edge, but not more than 80% from the same edge. A range of 50-50 always divides the rectangle in half. The line is always drawn parallel to the short side of the rectangle - and it does only work on rectangles (and squares, of course.)
I think eventually this will be incorporated into Protrude, and both will be mashed into a Greeble suite. I need a few days to work on the User Interface.
Daniel asked about what happens on curved surfaces. Since curves are really just softened rectangles, the plugin happily divides them using the same algorithm.
And Daniel's reply was to download the above model and produce this..