We've seen people use background revalidation to great effect, particularly in front of S3. You can get pretty close to one stale request per cache entry this way. And if-modified-since requests are really cheap.