Rick Moen found out the solution to this:

Basically, all of the HPLIP contents you actually want are in packages printer-driver-hpcups and printer-driver-hpijs. Install those, with the CUPS print engine, and you have full, working HPLIP. No 'hacking around a solution with each dist-upgrade' is ever required.

The point is: You simply do not need the package called 'hplip' (an omnibus metapackage that includes GNOME glue), and merely avoiding the error of installing it permanently (AFAICT) avoids dependency problems and GNOME disease.

lets remove hplip from recommends in cups (and any other package) and substitute it with printer-driver-hpcups and printer-driver-hpijs?