Sous linux il y a un package psutils qui contient (entre autres) un programme psresize qui fait exactement ce que tu veux sur les fichiers postscript.
pdf2ps te convertira ton pdf.

C'est du command-line évidemment, faut lire les manpages et expérimenter un peu.