How to save the data in a non-trustworthy db, so the next time I read from the db, I know that I've read actual and not an old version of the data?
I'm not a professional cryptographer, but you don't seem to be asking a cryptography question. Set aside the encryption part for a second, and I think you're asking for something impossible.


The two parties in your example are only communicating over the storage system. 
The only way they are alerted to new versions is by checking the storage system.
And yet, you also say that the storage system is unreliable, or can be hacked.


In that case literally anything can happen.

Even if both parties "remembered" the last versions they saw, either one of them could change the state of the system, do something bad, and then flip it back to an earlier state before the other one noticed. Or, a third party could do the same and fool both of them.

If you had one secure channel, you could use it to prove some things about an insecure channel. But in your example that doesn't exist.