I believe the simplest solution would be to create two nav menus in the Wordpress backend, then load different headers based upon the page the visitor is on.
Start by copying your header.php 2 times, giving your three header files. Example: header.php, headerA.php, headerB.php
Now, open you original header.php and replace all the code with something like this:
<?php
if (is_page('contact')){
<?php include(TEMPLATEPATH.'/headerA.php'); ?>
}
elseif (is_page('gallery')){
<?php include(TEMPLATEPATH.'/headerB.php'); ?>
}
else {
<?php include(TEMPLATEPATH.'/headerA.php'); ?>
}
?>
This will tell Wordress which header to load, based on the type of page the visitor is on.
Also, make sure you load the correct menu in each header file using:
<?php wp_nav_menu( array('menu' => 'Menu A )); ?>