Let’s have a site wide version number that is changed every time something is updated and cache needs to be invalidated. This number is stored in a simple text file. Cache keys are made up of Request-URI and this unique key, which is passed around in a cookie VERSION_NO.
On every page request javascript calls version.php?timestamp (which is never cached because of the timestamp), which using stat() reads the last modified timestamp of that text file and compares it to the value of VERSION_NO cookie. If they are different, a new cookie value is set, which in turn changes the cache key for all future requests, and the cache is invalidated.
The only thing I don’t know is how fast and resource hungry is the stat() call?
Update: or would it be better to use filemtime()? There is a comment which says that 1000 filemtime() calls take 0.0049 seconds, which I think is very reasonable.