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.