After asking this question, it appears that a lot of CSS hacks and tricks are needed to achieve something that simple. People have said that CSS is broken.
So I wonder now, if not CSS, what are some alternatives to creating advanced html structure and markup/layout?
Are we left with tables and framesets? Or is there something else?
CSS is broken, but the best way is still CSS.
While CSS itself may have flaws and missing features and be generally crappy, and while it may not work the same in every browser, it's still the best tool for the job. Its still an extremely flexible tool, albeit a slightly broken one.