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.
The answers here already explain how the information might be disseminated to pilots if the change is planned well in advance. But what if conditions require changing the frequency in use without notice?
Many facilities have backup equipment for each frequency. If the controller determines that a problem with radio communications is on the ATC side (e.g. if they suddenly can't get a response from multiple aircraft) they can switch to the backup equipment and hope that works.
If the backup equipment doesn't solve the problem, many facilities have multiple frequencies they can pull up. Generally each control position is able to immediately change which frequencies it uses—these will not be manually tunable, but based on the pre-set frequencies that are hardwired to individual transmitters and receivers. Sometimes a frequency may be allotted to a facility for explicit use as a backup, while in other cases it may be a lesser-used or historically-used frequency; for example, one sector at my facility has a main radar control frequency, a secondary frequency, a frequency dedicated for guiding aircraft to the runway by vectors alone, and a "remote" frequency whose transmitter and receiver are located at a satellite airport. If aircraft are in range, any one of those frequencies may be used to communicate in an unusual situation. Generally each control position (each radar "scope" or "sector") will have one or more dedicated frequencies, but during times of slower traffic multiple positions may be combined and worked by a single controller; then all of the other frequencies become available for backup use. (This would probably only work in the approach and tower environments; in the enroute environment the transmitter sites would be too spread out to back each other up.)
So how do controllers tell pilots which frequency to use? Step one is to broadcast "in the blind" on the old frequency (on the off-chance it still works) and on the guard frequencies 121.5 and 243.0. In the US, the phraseology is Change to my frequency XXX.XX. Then the controller will coordinate with surrounding facilities/sectors and tell them to use the backup frequency instead of the normal one, and if possible/relevant will ask the tower advertise the backup frequency on the ATIS.
And finally, for a control tower in particular, there are portable tunable emergency radios stationed in the tower cab for use during an evacuation. The idea is that the controllers would grab the radios on their way down the stairs and would be able to provide rudimentary services once away from the building; of course they could also be used from within the building without evacuating. We've used ours that way when our main frequency was out of service: we tuned the portable radio to the main frequency, and if any pilots called on that frequency we would tell them to use the other one. (Again, due to the distances, this option is less useful for large approach controls and enroute centers.)