Can we use panels for header and footer?
Panels takes over the "Content" region.

Panels everywhere takes over the entire page, and is the module that does what you want.

Some themes are listed on the PE page as "compatible", but all that means is that they ship with appropriate templates, which makes it easier to get started.

You can use any theme you want with PE, but you will likely want to provide your own site-template as alternative to the regular page.tpl.php which PE will disregard. Look at one or two of the themes that are listed on the PE page and their use of template to get started.