Excuse my ignorance in this matter, but about the 'cache sub-key' issue, why not just use a generic cache (with some expiration model -LRU, perhaps-) with a 'smart' comparison function?
We could use as key full request headers (perhaps somewhat parsed), and as a comparison function a clever enough code to handle Vary, entity aging and so on. Best regards, -- Gonzalo A. Arana