XTS mode of operation and authentication I'm wondering if XTS is used (Random Access is needed) what the best solution for authentication is. If I wouldn't need random access, I would take AES-GCM or AES-CBC-HMAC but random access is a must.

What mode of operation would be prefered for random access with authentication?
I assume you mean "random access" by "decrypting arbitrary part of ciphertext, operate on it, and securely encrypting it again". 

The XTS mode is designed as a "Full-Disk Encryption" mode, which means it does not have the slightest concern with authentication. 

From practical perspective, I recommend having a keyed tuple or tree hashing mode for authentication. Some of which are specified in NIST SP 800-185. You may also want to check out Sakura tree-hashing encoding scheme. 

Update

Tuple hashing is a hashing scheme, where a sequence of bit/octet strings is hashed in such way, that guarantees the uniqueness of the output, even when otherwise their simple concatenation would have resulted in some ambiguity. For example, hashing the concatenation of "ab" + "c" would be the same as "a" + "bc", but the tuple hashing of $(\text{"ab"}, \text{"c"})$ would be different from $(\text{"a"}, \text{"bc"})$. 

Tuple hashing is usually sequential, but it doesn't always have to be. 

Tree hashing is an efficiently method for hashing long messages. Example include Merkle tree. During the SHA-3 competition, the Keccak team proposed the Sakura tree-hashing encoding scheme, to solve the shortcomings of various ad-hoc tree-hashing encodings. 

I added the "keyed" in the previous text to mean that they're supposed to be used as authentication tag.