One issue is that it's not easy to mix percentages and pixel measurements, because different screen sizes will behave differently. But it is possible to use API features to get the map to behave the way you want it to, on any size screen.
Make the map 100% of the screen size, so the header obscures part of the map. Suppress the default map controls so they do not appear partially obscured. Create an empty custom control the same size as the header and position it at the top of the map. When the map controls are added back, the custom control pushes them out of their usual place so they look right on the visible map.
var posn=google.maps.ControlPosition; // shorten the reference
// Add empty custom control
var controlDiv = document.createElement('div');
controlDiv.style.width='100%';
controlDiv.style.height='41px';
map.controls[posn.TOP_LEFT].push(controlDiv);
map.controls[posn.TOP_RIGHT].push(controlDiv);
// Add map controls
map.setOptions({
mapTypeControlOptions:{position:posn.RIGHT_TOP},
mapTypeControl:true,
panControlOptions:{position:posn.LEFT_TOP},
panControl:true,
streetViewControlOptions:{position:posn.LEFT_TOP},
streetViewControl:true,
zoomControlOptions:{position:posn.LEFT_TOP},
zoomControl:true
})
http://jsfiddle.net/GTscW/4/
Note 1: Because the map is actually 41px larger than it looks (in your case), the centre-point will be 20px higher than the centre of the viewable map. This may not be worth worrying about. If it is, then dealing with an apparent centre-point is the subject of another question on SO.
Note 2: This method won't work to get a fixed footer, because the Google logo and Terms links are always at the bottom of the map and [currently] don't move to avoid a control.