List User Online Status
You have a few challenges here.

As you say, pagination will be wonky if a user's status/score changes between page requests. You could use fragment caching to cache the rendered pages, and serve the same content to all users for a fixed period of time. But this has a different drawback: Rendering is lazy, so page 2 (or 3, or N) will only be cached if someone requests it. So that's the same problem as before; sorting may change. Also, if the cache updates between page views, it doesn't matter that you're using a cache, since it's not that same cache version as was used in the previous request.

So what you'll want to do is run something that periodically rebuilds/-queries the entire list, a multi-version cache, and a way to lock a user into a specific version for his/her subsequent page views.

The tradeoff (besides more work) is that the list will be stale after a while.

An example of this is stackexchange's rep leagues tables which, while based on score, lags a bit behind actual score. You can decide whether that's worth the tradeoff.

Now, for querying periodically, I'd recommend


using an ActiveJob task to do the querying at fixed intervals
storing multiple versions of the query results as a hash in Rails.cache, using a timestamp as key for simplicity
a way of cleaning out old results, so stuff doesn't keep accumulating
adding a param to page requests to identify the active cache version/timestamp (if blank, serve the latest)
some means of telling the user "we're serving you a snapshot of this list as of [time and date]" - and a way of saying "the snapshot you requested is too old, and we've thrown it away"


In the end, it's simpler to only show unpaginated (but limited to top-N) lists with no caching. Or show lists that use a (more) stable sorting parameter (e.g. user name).