Is is safe to use MtEtM? (MAC-then-Encrypt and Encrypt-than-MAC) Assuming I am using different secrets/keys for each MAC pass, does running both MtE and EtM creates any vulnerability?
This is what I mean about doing MtEtM:
K0 ≠ K1 ≠ K2
addMAC(msg, K) = msg || MAC(msg, K)
ciphertext = addMAC(encrypt(addMAC(msg, K1), K0), K2)

If I understood correctly, EtM has the advantage of ensuring that the recipient doesn't even use the decryption key when a message is tampered. But MtE is harder to forge.
Intuitively it sounds that combining both would make the system at least a bit more secure, but I am worried about some sort of timing attack.
Also, is the use of HMACs instead of generic MACs here a potential problem?
If the MAC is theoretically secure, but its implementation has a side channel (like by Differential Power Analysis, maybe even timing) leaking information about the MACed message (but not the key), and the encryption is secure including it's implementation, then neither MtE nor MtEtM are safe (because the side channel leaks about the message), but EtM is secure (because the MAC is applied to ciphertext, which can safely leak).
Thus EtM can be secure when MtEtM is not. A better reason to prefer EtM to MtEtM is Occam's razor.