That sounds good.
I actually was thinking about chunks of multiple sizes before you mentioned it! Since your levels are going to be gridlike to begin with you could get away with having chunks of any size. To keep things sane, you could require that they are all square, though rectangular chunks could allow for more variety--it would just make the random distribution trickier.
The rules for detailing each room are where the real interest would lie. One thing you could do is try to equally distribute powerups throughout the level. Use a pathfinding algorithm to find the quickest path through the level and then drop powerups every n
steps (plus or minus a random fudge factor) along the way. This would keep the levels "fair" and avoid concentrating powerups/items too close together.
Something else that occurs to me is that you could add a lot of variety by having multiple tilesets. So you'd have a set of predefined chunks which are just arrangements of walls, but you'd randomly choose a tileset for each level's graphics, so each level would have a "theme." Combined with random decorative details, the same chunk would look decidedly different between a snow level and a desert level, with different decorations, powerups, and orientation.