Constructing a custom protocol using well-vetted algorithms? For the reasons I cannot go into details, I need to design my own protocol and overall security system which will be used to establish secure data exchange between various devices (most notably desktops of all three major OSes, Android and iOS devices and Raspberry Pi, with the possibility to extend it to other embedded systems). Since I wouldn't dare to do my own crypto algorithms implementation, this implies that I have to rely on tried and tested libraries available for those platforms (i.e. OpenSSL, BouncyCastle, CommonCrypto, …) so I settled with what they all support - RSA for signing/authentication, DHE/ECDHE for session establishment, AES for encryption, PBKDF2 for key derivation and SHA2 for general hashing needs. The key sizes and complexity will depend on the hardware ability of targeted platforms.

Now, I've done a fair bit of implementations of existing protocols and I like to think that I know my way around cryptography and perils that await if not applied properly, however I wouldn't dare to consider myself a cryptography expert and thus I decided to query the hive mind. Of course, once everything completed it will be properly audited and tested, but for now I need to know if I'm on the right track, that I haven't done some glaring omissions and if it is possible to improve it even further.

The system I'm building should both cover the storage on devices and the communication between them and to preserve forward and backward secrecy.

For the storage part I plan to utilize AES in CBC mode, storing the randomly generated IVs with each individual encrypted file. The 'master' key itself will be randomly generated and also AES-encrypted using a key derived from the user's password using PBKDF2, stored along with the salt and iterations used in it. My main concern is the IV part as if generated randomly it might repeat thus compromising the encrypted files if they happen to be similar enough or even the same. It's quite a low chance buy I don't like leaving anything to chance so the question is - given that the IV is public knowledge anyway, is it safe to use incremental progression/timestamp as IV in this case?

The communication part will be a bit trickier as the devices will never communicate directly - instead the data exchange between them will be relied through a third party database to which they periodically connect, which is one of the prime reasons I'm designing my own protocol. If we except this oddity, the data exchange itself should function quite the same as if they were communicating directly, namely the devices will establish a session each time they 'contact' each other and then use the session key for encryption.

To establish a session I plan to use a variation of STS protocol adapted to this environment. The only oddity here is that in some instances only one of the parties involved in communication will posses the RSA key of the other so it won't be fully authenticated - my understanding is that even in this case no successful MITM attack can be performed as at least one of the parties will reject communication if the signature doesn't match. Is that a safe assumption?

Once DH/ECDH keys are exchanged an actual session AES key will be derived from them using SHA2 and the rest of the data exchange will be encrypted using that key, again in CBC mode - until the session expires, when the process repeats. I'm still not clear on how to approach the message integrity and authenticity verification - at first I thought that signing the message with the device's RSA key will be enough, but since it may happen that only one of the parties has the other party's certificate I might add a HMAC alongside with the exchanged messages as well. What would be a recommended, cryptographically secure way to handle that?
You might want to start by reading Lessons learned and misconceptions regarding encryption and cryptology.  I spotted 3 potential issues in your proposal that are explained there.

Instead of designing your own cryptosystem, you should try hard to use an existing well-vetted scheme, like TLS or DTLS for interactive communication, or GnuPG for storage or store-and-forward messaging.  The fact that communications are routed through a proxy server doesn't change this recommendation; you can still do end-to-end cryptography.

(If you are building your own protocol, you to use authenticated encryption, and deriving cryptographic keys from a passphrase tends to provide poor security.)

Since you haven't given us any specifics why you can't use existing schemes, it's going to be tough to provide you with more detailed advice.