It's definitely do-able, just takes some creative templating.
In your HEADER template, replace the logo with a table containing two rows. The first row will be your logo with background. The second row will be your gray navbar.
Open the NAVBAR template, and remove all the navigation and related popup/javascript code with it, and place it in the second row inside your new table.
Then make sure $spacer_open is still at the bottom of your header, and you should be good to go. I know it sounds really broad, but it's the best I can describe it without taking a lot of time to sit and go into detail

I'm sure you can manage.