Is there a way to hook on cache clearing?
The way to do this is to use hook_flush_caches in combination with register_shutdown_function. Example code:

/**
 * Implements hook_flush_caches().
 */
function mymodule_flush_caches() {
   // After caches are cleared we will run mymodule_cache_rebuild()
   register_shutdown_function('mymodule_cache_rebuild');

   // We don't want to add any custom cache-tables, so just return an empty array
   return array();
}

/**
 * Rebuild expensive cache items that need to be rebuilt immediately.
 */
function mymodule_cache_rebuild() {
  // Do the cache rebuild work here
}


Using register_shutdown_function means that our cache-rebuilding function will be called after the caches have been cleared. We are abusing hook_flush_caches in a way that it was never intended to be used, but this should do exactly what you need.