As for automatic testing, what you are missing is the capability to either

a. Regenerate the datastore in a very specific state during the testing phase, so you can provide each test with the required data and the required state. If we were speaking about databases, I would suggest implementing in-memory databases alongside with some sort of change logger.

b. Mock dependencies. 

What you are looking for is named **determinism**. For you to be able to execute tests in any order, anywhere, anytime and always obtain the same results you need the capacity to force the data that makes the business logic to behave in one or another way.

> Another example would be testing authentication and other endpoints
> that require an authenticated user. So to perform those test that
> require authentication, such as a request to user/update I would need
> to have an API token ready for it, which means I must have run the
> auth/login request to get the API token and saved it somewhere to be
> used by subsequent tests. Therefore, it obviously introduces the same
> problems as the above-mentioned example, if not more.

Hell no.

You can create a default token for testing. One which never expires and bound to a non-production user. For example, I have tests that help me out to create and validate JWT. Those tests are never executed as part of the testing plan. They are tools somehow. 

I turn these tokens into constants in my testing code. If I have different profiles, I generate different tokens, each of which is bound to a non-real user with the expected role for the test.

> Hence the current organization necessitates a rigid sequence of tests,
> which goes against the principle of atomicity, which in turn renders
> features like parallel testing impossible. 

Not necessarily. Say you achieved **determinism** in your automatic testing. You still can deploy a staging environment for E2E or Loading testing where the kind of tests you have described fit well.