Page title with substitution on views page
You can't change the route object in a hook. Use a RouteSubscriber to add a dynamic _title_callback to the view route.

Otherwise setTitle() should work. The bug you've described is not a bug. It's about caching in general. When you add dynamic data you also have to add the cache metadata, which defines what kind of dynamic data this is.

For example if the dynamic title depends on the node 123:

$output['#cache']['tags'][] = 'node:123';