Thanks for pointing me in the right direction.
I did the following now:
I used http://www.freefontconverter.com/
to convert the ttf into a .pfb.
I copied the pfb into /usr/share/ghostscript/fonts/
I added the following line to the fontmap file (located at /usr/share/ghostscript/<gsversion>/lib/Fontmap):
Then I used the following command to embedd the font:
gs -dSAFER -dNOPLATFONTS -dNOPAUSE -dBATCH -sDEVICE=pdfwrite -sPAPERSIZE=letter -dCompatibilityLevel=1.4 -dPDFSETTINGS=/printer -dCompatibilityLevel=1.4 -dMaxSubsetPct=100 -dSubsetFonts=true -dEmbedAllFonts=true -sOutputFile=output.pdf -f test.pdf
When I print via lpr the font is now correct... but I have a new problem, the "margins" on the paper are not the same.
When I print it via lpr everything is like 1 cm displaced (to the bottom), but when I print (the same pdf) with adobe (on windows) its correct.
Any advise on that?