In the meantime, I’ve gone for a) low cache time – 60 minutes, plenty enough to have good performance though, and b) disable cache for logged in users only. This seems to be a satisfactory solution to me.
I also found, under heavy load, that Super/Total cache didn’t help a great deal, while Quick Cache had a massive impact. YMMV though of course.
As well as being cache-friendly, this solution would allow the possibility of locally updating, so if you switch to another tab in the browser and switch back a few hours later, the “1 minute ago” can change to “3 hours ago”.