Here are some contributions. I'm not familiar with Java and Spring, but I believe these guidelines are valid regardless of your technology stack.
Stay away from sessions for authentication
As you anticipated in your question, avoid using a session to authenticate users. Sessions are peremptory and it's very difficult to replicate it consistently in a distributed, scalable infrastructure.
Also, load balancers don't work well with sessions: see Problem with Session State timeing out on Load Balanced Servers.
Use a token-based authentication system
A stateless app will preferably use a token-based authentication system. Firebase is a good example. Map the immutable user ID extracted from the token to the user data persisted in whatever storing mechanism you want to use. Since this user ID won't change, you'll be fine in a distributed database.
Don't confuse stateless with 'data persistence'-less
Sometimes people think that, by mapping a user ID to user data in a database, you are making a stateful app. It's not true. Let me make it clear:
An application that persists user information in a database and has dynamic responses for authenticated users IS NOT NECESSARILY STATEFUL. Stateless means the app won't have to distribute mutable authentication sessions across multiple servers and won't change its internal state to a particular client depending on session data.
The trick of stateless is: once a user validated its token by logging in, the server don't have to distribute anything new across the database servers and it won't change its state to that client. It can extract user info from the token and carry out what's needed to answer the request. If the token expires, the client will require a new authentication, which will generate a new token, but this is isolated from the app server, since the user ID will remain the same.
Use cookies for caching while remaining stateless
If caching in cookies some frequently requested data will improve performance, that's fine, go ahead and cache. Just make sure the cookie isn't connected to any server state and your app will not break if the client loses the cookie.
