UPDATE: Now if you're interested in this, you should sign up for Google AdSense for Ajax, which provides exactly what you want.
As both of the other answers state, refreshing your AdSense advertisements automatically isn't allowed. I understand that you only intend to refresh the ad in response to user action, but it still isn't allowed, even though it should be!
Remember, the reason why you want to update the advertisements is so that you can show new ones. Displaying an advertisement is called an "impression." When you use code to refresh the ads, you are automatically generating ad impressions.
AdSense Program Policies state (emphasis mine):
Invalid Clicks and Impressions
Clicks on Google ads must result from genuine user interest. Any method that artificially generates clicks or impressions on your Google ads is strictly prohibited. These prohibited methods include but are not limited to repeated manual clicks or impressions, using robots, automated click and impression generating tools, third-party services that generate clicks or impressions such as paid-to-click, paid-to-surf, autosurf, and click-exchange programs, or any deceptive software.
Refreshing your advertisements is a violation of the letter of the rule against generating impressions. With that said, I think any reasonable person would agree that refreshing advertisements in an AJAX app in response to user behavior (e.g. in response to a click) isn't a violation of the spirit of the rule.
For example, imagine rewriting your entire app to stop using AJAX. That's clearly a worse experience for your users (it's slower, the page flashes on every click, the page can't dynamically update in the background), but, by a technicality, it's not a violation of the AdSense Program Policies.
Clearly Google meant to prohibit automatically replacing the advertisements every five seconds (creating a "slideshow" of advertisements). Google also meant to prohibit making your site look more attractive to advertisers by appearing to have more visits than you actually have. I'm sure they didn't intend to prevent you from designing a high-performance AJAX website... but unfortunately sometimes rules have unintended consequences.
Of course, as you originally pointed out, you CAN still refresh your advertisements if you embed them in an iframe and modify its location. (Here's how to use iframes in an AJAX application to refresh AdSense.)
You rejected iframes in your initial question, perhaps because you knew that using iframes would violate Google's policies... but if you insist on breaking the rules, you might as well break them all the way! ;-)
Ultimately, I think you'll find that generating impressions this way isn't worth the risk: you'll "refresh" the ads only to find that Google is just showing you the exact same ads as before.