I think using a template file will be the easiest way to do this.
In your view
=> Select the tpl file that suits you best
=> place that tpl file in your templates folder under your theme
=> for the content of the file
=> under Theming Information in your view click
=> copy that content to your tpl and change the position of your header
=> come back to Theming Information and click
Rescan template files - your newly added tpl(under your theme directory) should be highlighted(bold) now, which means you tpl is up and working!
Hope this helps.
[I am sure you might know how to do all this, yet putting it in details might help somebody else looking for the same solution who hasn't yet learned how to :)]