Ok, I'm new here in the forums. So be gentle 
From what I understand:
You have a naviation menu (with our or with out images) and you want it to appear across multiple pages, and you want to make it so its really easy to manage and update? So you could just change one file and it would change across all of them? You could do this quite easily with frames as you say and I"m pretty sure you could stick them in a table so.. something like.
Code:
<table>
<tr>
<td>
frame code in here that links to navigation.html
</td>
</tr>
</table>
Then you could just copy and paste that chunk of code onto each page that requires the navigation. I dont actually know the iframe code off by heart, but im sure it has options like NO BORDER or NO SCROLLING or something to make it 'appear' seamless in the page.
The other option and much better in my opinion is to use PHP includes. But that requires a php webserver (which yours probably is actually) and a little bit of knowledge of php. But I'd be happy to share it with you if you'd like. Hope this helps in some way or another.
Tristan