The Master page is useful for containing things like headers, copyright text and menus which don't change from page to page within a site. I wouldn't give up oin them or you will regret it when you go to make changes to your site layout.
To answer your question, if you have AJAX, great use this. Also, consider the simple upgrade to ASP.NET MVC. It will make your life a lot easier and solve a lot of your problems by forcing you to consider your pages in terms of Views and the data insertion in terms of Actions.
The master page provides contentplaceholders for the content that the pages contain. You can provide a default menu in the masterpage and override it on any of your pages.
Menus are a special case where they often change depending on the page that you are on. If this logic is relatively simple, then you could put the menu into a UserControl (ASP.NET) or View (MVC) and allow the control/controller to determine what data to put into the menu for display to the user.
Regarding full page reloads: If you are using AJAX then there will not be a full page reload. Furthermore, if you are using MVC then a full page load becomes less of an issue as there is no viewstate and the markup is a lot lighter. Look at the markup of Stack Overflow. I believe that it is an MVC site. Of course, it is usually better not to do a full pageload if it can be avoided and AJAX enables this. I am just saying that MVC makes it less of an issue.