Do you realize that in a 1024x768 monitor, your logo won't fit between the sidebars? I'm not sure if that's the majority of existing computers, but if you do what you suggest, you will make it impossible for a vast number of people to see your site properly/comfortably.
Anyway, assuming you work around that problem, the basic situation is that tpl_header.php needs to run first to output message alerts above the top of the regular page, so it can't just be moved into the table structure as is. All of the header output code could be moved to another (center column) file, and display between the sidebars, while the header div would disappear from above the sidebars.
The gentler way to do it, without getting into detailed specs, is to make #headerWrapper absolutely positioned, with 100% width, left padding = left sidebar and right padding = right sidebar. Absolutely positioned elements take up no space in the page layout, so the header area would shrink to nothing and the rest of the page would move up to the top. Give the center column a margin-top = header height, and it will drop down below where the header is sitting.
There may be other complications in getting it perfect, but I believe this plan will do the job.