Assuming your server is running Apache and PHP, you can tell your server to parse all your .html files through PHP without changing all your file extensions.
Just add the following line in your root .htaccess file (depending on whether your PHP install is running as an Apache module or CGI mode):
# If PHP is running as a module
AddType application/x-httpd-php .html .htm
# If PHP is running in CGI mode
AddHandler application/x-httpd-php .html .htm
After you add the appropriate line, all .htm and .html files will be executed the same as if they were .php files. From there you can insert your headers and footers in your existing HTML files like so:
<head> <!-- HEAD CODE --> </head>
// Include your custom header file
<!-- Body Code -->
// Include your custom footer file
Then just create header.php and footer.php with whatever HTML you want inside, IE: navigation links, footer links, etc.