Before you start tearing out your hair: Do you need to make a rule? How many humans don't send this header? That is: how many of your own, particular humans? (I specify this because I myself get human visitors that would get auto-blocked from many sites. It's about the visitors you yourself want, not the ones that someone else might want.)
A quick riffle through yesterday's logged headers suggests that the only ones who don't send Accept-Encoding --with gzip somewhere in the list, usually first-- are second-class robots.* You don't really need to make life easier for them, do you?
* The major search engines must all send the header, because they didn't come up in a quick-and-dirty search.
mod_deflate should look for the Accept-Encoding header and compress if acceptable based on how your output filters are configured.
My CMS compresses all htm and js files on my own computer and uploads to the server the compressed files.
are these compressed files uploaded as .gz file types? are you also uploading the uncompressed versions?
you should only use "AddEncoding gzip" for the gzipped versions of the files and you need a way to serve uncompressed versions. i don't really see a clean way to reinflate/decompress the output of a precompressed resource based on the Accept-Encoding header.