I'll only address distributed monitoring. Use NSCA instead of NRPE. That bypasses the limitations of the Nagios active check scheduling. I have a wrapper that I use for that:

http://rbcarleton.com/send_nsca_service_check.shtml

Use some kind of automation system like CFEngine for the distributed scheduling. Some assembly required ;)