UTXO is complicated but definitely a very good solution as it completely eliminates replays (while still allowing re-attachments).
“Nonce” works (Etherium is the living proof) but they require to store the last used count for every spent address, even across snapshots. Unfortunately, this sounds like the current SpentAddresses. There are ways to discard (and thus allow replay attacks) once the balance is below a threshold value, but this sounds like very difficult UX for example.
Including Trunk and Branch in the bundle essence (and thus effectlively disabling re-attachments for anyone but the original issuer) does not offer a sufficient protection as the bundle can still be replayed with the same Brach and Trunk and then promoted (at least if it is not belowMaxDepth).
Signing everything should work, as only the exact same bundle can be replayed with gets filtered out. Again, in this case re-attachments can only be performed by the issuer, which could be a very reasonable compromise as this is anyway the case in 99% and especially in combination with the Conflict White Flag, re-attachment are hardly necessary.