Be aware that the PDF spec (as of version 1.7) runs to about 1300 terse and
informative pages -- so there's a lot of stuff in there...

   http://www.adobe.com/devnet/pdf/pdf_reference.html

I quote from the spec:

===================
An application printing a PDF document to a PostScript
device must follow these steps:
1.Insert procedure sets containing PostScript procedure definitions to
implement the PDF operators.
2.Extract the content for each page. Each content stream is essentially the
script portion of a traditional PostScript program using very specific
procedures, such as m for moveto and l for lineto.
3.Decode compressed text, graphics, and image data as necessary. The
compression filters used in PDF are compatible with those used in PostScript;
they may or may not be supported, depending on the LanguageLevel of the target
output device.
4.Insert any needed resources, such as fonts, into the PostScript file. These
can be either the original fonts or suitable substitute fonts based on the font
metrics in the PDF file. Fonts may need to be converted to a format that the
PostScript interpreter recognizes, such as Type 1 or Type 42.
5.Put the information in the correct order. The result is a traditional
PostScript program that fully represents the visual aspects of the document but
no longer contains PDF elements such as hypertext links, annotations, and
bookmarks.
===================

(A conversion which the spec describes else where as "straightforward" ;-)

That doesn't mention the fact that some PostScript operators seem ("seem"
meaning "that's how I read it, but I may easily be wrong") to have subtly
different definitions in PDF, which may complicate matters (although, at a
guess, you can get decent results by ignoring that fact).

My point is that doing it yourself is going to be a fairly big job.  There
isn't much in the way of free PDF parsers in Java out there (the only one I
personally know of is part of PDFBox[*]).  Other than that you can expect
either to have to switch to a non-Java solution (which I think you implied you
don't want to do) or to a commercial one.  The commercial ones all seem to be
moderately pricey -- O(1e3) $-US.  Note that the ability to parse PDF doesn't
necessarily mean that you get easy access to the structures needed to convert
PDF to PostScript.

   -- chris

[*] Although a somewhat limited version of JPedal seems to be available under a
GPL licence.