wp-postviews seems to be the most commonly used, but it requires modifying the theme (which would require creating a child theme to avoid being overwritten by theme updates) ...
If you want to actually display the view count on the post but this item isn't built in to your theme already, then you're going to have to edit your theme or create a child theme. There's no way around that.
...and does not seem to work with caching plug-ins.
If you're wanting to display a dynamic view count on a post, using caching isn't necessarily a good idea.
Most caching systems return static HTML content in place of a dynamically-generated page. This means the counter wouldn't increment with each page load unless you force the cache to refresh at a set interval ... and then the counter would only chance when that refresh occurred.
Seems like a common feature, surely this has been done somewhere?
It has, and you've already found one of the ways people have been doing it - WP-PostViews
There are a few other plugins out there that do the same thing, since you've already found one I assume you can find the others pretty quickly as well.