> Would it be hard to write a script which takes an eps file, runs it
> through LaTeX/psfrag, and converts the dvi output back into eps.

no, it's not hard (although I have only done it a few times by hand so
don't actually have a script for it). Basically this is the same process
(using dvips -E, that the latex->html converters do before making gif

That's also what you _have_ to do to use psfrag with pdftex. (So you
can distil the combined eps file to pdf).