What's the latest in the page lifecycle a module can send an HTTP header?
Headers can be sent anytime up until the content is sent to the page which happens in drupal_page_footer(). The whole page is output buffered: _drupal_bootstrap_page_header has the ob_start and drupal_page_footer has the ob_flush.

Headers are also overwritten by default so there is no reason why you can't re-send the Last-Modified header at any point.

So, how about hook_exit() (called from drupal_page_footer just before the ob_flush).