Lo habitual es la primera opción, y usando algún lenguaje de lado servidor incluir los ficheros que no cambian —cabecera/pie— en cada página individual —contacto/historia/etc.
Otra opción sería hacer eso mismo sin lenguaje de lado servidor y usar
Server Side Includes de Apache.
Tanto una como la otra, la idea es que sólo tengas un archivo para la cabecera y no tengas que ir pegando en cada página el código.