A slightly better one IMHO, would be to provide three packages instead
of two for each program: X, X-native and X-byte. X would provide files
independent from the bytecode/native status of the executable.
There we would have
zoggy 'Depends:'ing on zoggy-native (= 1.2xxx) | zoggy-byte (= 1.2xxx))
and cameleon would just depend on zoggy.
In the case of coq, I would provide files such as the emacs mode, the
standard library of coq in the coq package, and I would have both
coq-byte and coq-native as independent packages (and they would not
conflict since having both bytecode and native version makes sense for
coq --- thus I have to have a look at diversions...)