Perfect Deniability of a MAC
A Carter-Wegman -style MAC gives you easy deniability when you use a one-time pad to encrypt the universal hash. You can compute a hash for your fake message and choose the key accordingly, just like you do with the one-time pad that you use to encrypt the message contents.

This is actually available widely to programmers: NaCl has crypto_onetimeauth which uses Poly1305 (a polynomial evaluation MAC) with the latter half of the single use key used as a one-time pad. To get the same MAC value for another message you can just compute the MAC, then modify the pad part to match your target.

Not all uses of Poly1305 give you perfect deniability, however. The ones where the key or pad comes from AES (Poly1305-AES) or another cipher (e.g. crypto_secretbox) likely do not because you cannot freely choose the value of it without affecting message decryption or the authentication of other messages.