Integrity with anti-confidentiality
Sending information covertly when using legitimate systems is a well-studied field. As another question mentions, key words are covert channel and subliminal channel.

Designing systems with no covert channels is difficult, but not impossible. The main difficulty is to ensure that if any randomness is sampled incorrectly, the legitimate recipient must detect and reject.

For your case, deterministic signatures (as you had almost arrived at yourself) would be sufficient. The main interesting system is RSA-FDH (full-domain hash) which is trivially deterministic. There are also systems that have deterministic signature generation (if you sign the same message twice, you get the same signature), but where someone with the signing key could generate different signatures without the verification algorithm noticing.

For more complicated systems, this becomes much more difficult. For some symmetric cryptosystems, you can use counters instead of random nonces.