Since postscript files are just text files, you can
a) look at them with a text editor (check that they begin with %!PS IIRC)
b) read said text file into your own program, so you can merge your data with the already encoded bitmap data.
c) squirt the whole lot out to the printer.
Reading image.ps is no different to reading image.bmp, it's still an external file.
If you want to hide the conversion inside your program, then that's doable as well.
No doubt you could get the source code for bmp2ps and just incorporate that directly into your code.
I've no idea what you did, but this seems to indicate that your printer might not understand postscript.
http://en.wikipedia.org/wiki/HP_LaserJet_4
Any particular kind of garbage - like for instance the same as what you see when you view the poststript file or was it a different kind of garbage.