I basically print out a very light 'Loading' type page, which has a meta-refresh tag to tell the client to re-request it in a few seconds.

If it has completed whatever work it needs to do (in my case, execute a heavy database query and collect results, then cache them), it then displays the results (which are now in the cache), if it hasn't completed it, it spits up the 'Loading' page again, set to refresh again.

(update:) The basic logic is as follows:

if (page_is_in_cache) {
  display page.
}
elsif (flag_is_in_cache) {
  page is being rendered, display a 'loading' message with a meta refr
+esh
}
else {
  set_flag_in_cache
  display loading page
  render page
  stuff page in cache
  clear flag in cache
}
[download]