For instance, if client application A talks to the service using version 1.0 of the API and client application B talks to the service using version 2.0 of the API, then those client applications can't interoperate because they are seeing two different sets of resources.
Your solution isn't far off the approach recommended by everybody who rejects the different URI approach. You don't need an API version header. When your representation format for a resource changes, provide a `version` parameter for the media type. For example: `Content-Type: application/vnd.example.foo+json;version=2`.
This is exactly how HTTP and the `Content-Type` header are supposed to work – if your representation for a resource changes, you don't change the URI, you change the media type.