Did you try with different resolution settings for the gutenprint driver? According to www.linuxprinting.org the recommended driver for the HP LaserJet 4 is "hpijs", did you try this driver?
-- output is scaled up to twice the size in laserjet 4 https://launchpad.net/bugs/53108 -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs
