Operating on the presumption that P&W currently tries to calculate update for all nations at once I'd propose the following system to fix the lag at update. Add two fields to the database:
Last update cycle (i.e. long int): Hold a number indicating which update cycle the nation is currently in.
Active since last update (i.e. boolean): Holds a flag to indicate whether the nation was active in the last update cycle (user logged in, was attacked, etc.)
As you hit update and the cronjob/timer runs the update script, you instantly update all nations which were active since the last update. These are folks who are most likely online or to be attacked and should be a few hundred nations at most. This will most likely cause the server to choke up for a few seconds as it currently does but should process fairly quickly. Now wait for a minute or two as folks run their attacks, the server will see heavy load and you'll be queuing up a lot of user-induced DB operations.
In the meanwhile, if a nation which is still in the previous update cycle sees a "hit" (login, someone views nation page, etc.) you instantly run the update queries for that nation and present the updated page, this should be fairly limited and avoid heavy throttling as currently occurs.
About 5 minutes after update, you make a list of nations still in the previous update cycle, and you queue up update for them in batches of 50 or 100 and run them at a steady pace (i.e. 50 nations per 15 seconds) that's quick enough to get through all nations but slow enough to avoid excessive server load.
Advantages of this system:
P&W stays available throughout update.
Peak load on DB server is minimal.
Almost no one will notice any side effect other than maybe an increased page load time if they view a non-updated nation.
The need to update "inactive" nations on first view will throttle the speed at which users can run blitz attacks at update, making it fairer to people with slow connections.
Disadvantages of this system:
More back-end logic.
Slight overhead by requiring checks.
Might need more frequent integrity checks (i.e. once a day) to see if no one is left behind in an older update cycle.
Large batch API calls might be tricky to combine with this sort of system around update.