I was able to solve the above problem using the Nginx ngx_http_userid_module. The hardest part was actually finding the module, implementing the solution was quite trivial.
I used their example configuration:
userid on;
userid_name uid;
userid_domain example.com;
userid_path /;
userid_expires 365d;
userid_p3p 'policyref="/w3c/p3p.xml", CP="CUR ADM OUR NOR STA NID"';
And then added the userid to my fastCGI cache key:
fastcgi_cache_key "$scheme$request_method$host$request_uri$uid_got";
Hopefully this answer helps someone discover this useful module quicker than I did.