It's exactly as RESTful and cacheable and stateless as common websites, eg the HN frontpage or a newspaper homepage. I think your bar for when something is RESTful or not is too high to be useful.
Why?
The server doesn't need to know if I already requested any previous page when I request page 9.
And if the data doesn't change it can easily be cached.
"Rest in Practice" (if I'm remembering the right book) would disagree strenuously with you.
Once you're doing REST instead of just "somewhat sane JSON responses" then the response has self-descriptive elements, including links to related resources. And importantly, URLs for older resources become static very, very quickly. Not unlike the internals of subversion or git.
The trick there is to realize that O(1) = O(2). If you're trying to show 25 items per page, you do not need a query that returns the most recent 25 items. That creates a situation where every single interaction is distinct from every other interaction.
Asking for 25 results and everything newer than that is barely more complicated than pagination already is.
Using that logic you can only have restful APIs if your application is useless and data never changes (which is fine for me, I hate debates about restfulness)