Randomly partition an rectangle into N smaller rectangles
Here's a simple idea that I believe can generate all partitions.  There are two types of subdivisions:


Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles.  (The usual "split in two" rule.)
Given a rectangle, randomly generate a rectangle that fits inside it.  Consider the 4 corners of this inner contained rectangle: for each of them, flip a coin and draw a line from this corner outwards towards the outer containing rectangle, with the direction of the line (horizontal or vertical) being determined by what the coin says.  Regardless of the directions of the 4 lines, the result will always be 5 rectangles.  (Some partitions that can be generated by rule 1 can also be generated this way -- in fact, only 2 of the 16 possible configurations of lines will produce partitions that could not be produced by rule 1.)


At any point in time you will have a set of rectangles (initially, just the original one).  Randomly choose one to subdivide (or you could, e.g., choose the biggest, etc.), flip a coin to decide which of the two rules to apply to it, and then apply that rule; keep doing this until you have $n$ rectangles.

Disclaimer: I have no idea how to even think about the set of all partitions, let alone whether the above procedure generates them all with equal probability...  Probably not.