In order to solve that, one would need to introduce separate timestamps for all storage items, which now becomes similar to solutions proposed in the original post.
Instead of maintaining the timestamps of all storage items individually, can we collect the storage rent in epochs(common expiry date). Any user who wants to store some data on a contract can pay for rest of the current epoch and next epoch(optional). At the end of the epoch, if the data is not paid for the next epoch then it is removed from state in which case, witness has to be provided for reviving the removed data.
PS: I have written a model for rent collection based on epochs here.