Wouldn't the audit interface offer one alternative? It's already used for tracking file accesses for readahead optimization.
The downside, of course, would be that some daemon would have to run in the background to collect the audit data. However, that could still involve less overhead than updating atimes on every filesystem read.