I am not sure that your database example protects you from shared state.

Whether it is a singleton or dependency injection, there is still only one database object that is being used all over the place. It doesn't matter how all the different classes get hold of that database object, they are still all sharing its state.

DI helps to decouple the various classes so they can be reused, and it can help with mocking for unit testing. But if you want to get rid of shared state, you probably need to look at functional programming and using immutable objects wherever you can.