I forgot the syntax or tags for this, what tags do I use to create and edit just one master page with headers and footers on it, so that I can just edit that one page and have all my changes to headers and footers appear on multiple pages across the site?
If your shared host doesn't allow basic .htaccess directives, it's time for another host! :-)
Php includes would be perfect for your situation.
It will work, but I wouldn't say perfect. PHP is a rich server side scripting language, to use it just for basic includes is overkill. Additionally, you have to mod the server to parse all .html/.htm files as PHP, which can give you some unexpected results - or change your files to .php extensions, which means you have to address SEO issues for existing pages (i.e., all your URLs have now changed and you need to 301 the old ones.)
so it will make a different footer (such as a page-specific menu in a consistent format) for each page
No code samples handy, but yes you can do this, and can even reflect "the current page" via environment variables. An easy way to do the first is just change the directive to point to different footers.
Parsing html as SSI has a lower overhead and it's the right tool for the job - not perfect either, but closer. :-)