Мне кажется, самый простой способ - создать внутренний div внутри исходного div и инициализировать карту для внутреннего div. При уничтожении карты просто удалите внутренний div и все.
var $inner = $('<div style="width: 100%; height: 100%"></div>').appendTo('#map_div');
// creation:
var map = new google.maps.Map($inner[0], { ... });
// removal:
$inner.remove();
без запроса:
document.getElementById('map_div').innerHTML = '<div id="inner_map_div" style="width: 100%; height: 100%"></div>';
// creation:
var map = new google.maps.Map(document.getElementById('inner_map_div'), { ... });
document.getElementById('map_div').innerHTML = ''; // removal