Problem: want to encrypt messages/objects/files using AES-GCM with the same secret key in a safe way, but want to do it in distributed/stateless way, so the IV of previous encryptions with the same key are not known and as I understand AES-GCM is not so secure with many messages if random IV is used.
 

*Would example of this solution be secure?*

1) For each encryption generate 16 bytes random salt (16-BYTES-RANDOM).

2) TMP-AES-16-BYTES-KEY = HKDF-EXPAND-SHA1(STATIC-AES-KEY-16-BYTES | 16-BYTES-RANDOM, 16)

3) Write in message first plain 16 bytes generated random.

4) Use the TMP-AES-16-BYTES-KEY to authenticate first 16 random bytes and encrypt secret data and add tag using 12 bytes IV all zeros.

To decrypt do the opposite - derive temp key from message random and secret key.