Thanks for your help IPalindromel!
I have found a way to correctly print with Photoshop 5.5 (which was my main problem). With a print preview I would have changed the scale (%) of the output to fit into my A4 page. It is what I do on OS X but I guess this is not the good way to do it. At least on System 7.
Instead, I go to the menu Image > Image Size and, here, I can see and update the size of the printable area of my document. It automatically re-calculate the whole document size as soon as you modify one of these values (width, height or resolution).
BTW, I have setup a network printer through Netatalk on my Linux VM. If you do so, make sure that on your classic Mac OS, on the print dialog, you go to the Photoshop settings and chose "JPEG" for the encoding instead of "Binary". Otherwise the printer server will throw an error.