Eu não tive sorte com o pd2fps.
Com o pdftops versão 0.12.4, empacotado com o poppler eu posso encontrar texto no código PS, mas apenas uma palavra por vez (cada palavra é cercada por parênteses).
Por exemplo, faça o download
wget ctan.org/tex-archive/macros/latex/contrib/lipsum/lipsum.pdf
pdftops lipsum.pdf
sed 's;2011/;2012/;' lipsum.ps > lipsum2.ps
Isso mudará o ano (presente no início do arquivo) de 2011 para 2012, mas preste atenção, porque nem sempre é possível alterar o texto, dependendo da estrutura do código PS, pode não haver espaço suficiente para substitua o texto. Experimente o exemplo anterior com 2013 em vez de 2012 e você verá.
Eu não entendo postscript, mas eu suspeito que alguma conversão pode levar a um arquivo de texto parcialmente binário e parcialmente, se assim for tentar usar sed que vai deixar os bytes não textuais como é.