Citnarf I like your example, very inspirational. I was messing around with dungeon generation after looking at your example and came up with a few ideas.
For the rooms, box objects would work well to define them. Then to draw the map with walls and floor just sample locations say every 16 pixels over the boxes. If the location overlaps a box then it's a floor, or if the location doesn't overlap a box in any of the 8 directions around it, then it's a wall.
So all that's left is to do is create a number of boxes, of random size and build onto already placed boxes. I found the "push out of object" actions of the custom movement behavior to be useful in this situation. My Pseudo code for box placement is as follows:
1. create a new box so that it overlaps existing boxes.
2. push the new box out of the existing boxes so it isn't overlapping but is next to other boxes.
3. move new box toward the closest box by a small distance. (this helps eliminate isolated rooms).
Here is the result of this interesting idea and some free time, enjoy.
http://dl.dropbox.com/u/5426011/examples/mapgen.cap
req 0.99.91