As I detailed in my blog post descriving the page cache issue, Drupal caches every request on the basis of the URL and content-type. I worked around it by changing the URL on every request but this is a temporary issue and a potential security risk since one can get the cached response of an authenticated user by simply guessing the URL (or even not that if someone isn't using a timestamp/some other key) so I figured that has to be a better solution.
After playing around with REST and Basic Auth which comes with Drupal 8, I noticed that it doesn't have the same problem. Curious, I looked into the services container (core/modules/basic_auth/basic_auth.services.yml:7) and noticed that it defines a service which disables PageCache for any Basic Auth request (core/modules/basic_auth/src/PageCache/DisallowBasicAuthRequests.php). And voila! That was the fix I needed, I've implemented it into my module here.