How to rebuild a cached page when it expires?
If you know what functions need to run in order to warm a cache, checkout httprl. httprl_queue_background_callback() is the function to look into using. Simple example of calling watchdog in the background http://drupalcode.org/project/httprl.git/blob/24a88acd2180191d0b54696e577f14615e37302d:/README.txt#l268

In terms of graceful varnish cache clears this has a good example: https://www.varnish-cache.org/trac/wiki/VCLExampleGrace Example of it in use: http://groups.drupal.org/node/63203