You mention PHP, which can be used to have common elements across a site. You can include a separate PHP script with the
include() function, which can include a separate script that draws the navigation. Or you can implement a whole template system, like Smarty, which gives lots of control.
You will have to add some HTML (or PHP or JS if you go that route) to each page, but only a small call to an external source. Ideally the call to the included sidebar won't change in the long run, and any changes to the sidebar will be done in the sidebar file (one edit that updates the sidebar across the site).