I've dug a bit deeper into the documentation and it seems like proxy_no_cache and proxy_cache_bypass should somehow do the trick, but I can get things to work with my exact scenario.
Here's the flow I'd like to create:
1. when a new user reaches the site, it is forwarded to the backend and receives a few cookies back.
A "new user" is identified by a [b]lack[/b] of a certain cookie, which is something I couldn't figure out how to implement (seems like it only supports bypassing/no caching if a cookie exists, but not if it doesn't).

This request should not be taken from the cache, but the response can be stored in cache as long as further requests will not be sent the cookies this request produced.

2. Returning visitors can be served from the cache, unless they are logged in (in which case they should be sent to the backend and the response should not be stored). This is simple enough to do with the regular bypass/no_cache combination based on a cookie that is created when a user logs in.

----

It doesn't seem like a complicated scenario, but I can't get it to work just right.
Any help would be appreciated :)