What is the policy for ATC towers to notify aircraft the frequency they broadcast and monitor on has changed? How do they do it, if radio isn't available (because they just changed their frequency)?
ATC frequencies don't change very often, but when they do they are planned well in advance. NOTAM's are issued ahead of time to let people know, and if the airport has ATIS they will include the new frequency on the ATIS.
If it is an enroute frequency, the other controllers will simply hand you off to the new frequency, and you don't even need to know about it ahead of time.
A Notice to Airmen (NOTAM) will be issued for the airport pending a charting change. If you subscribe to a charting service like Jeppesen, you will get a change notice from them and updated approach plates with the new frequency.