В уже готовый pdf - ИМХО никак. Только пересобрать документ заново. Можно научить просмотрщик документов подставлять шрифты, но это зависит от viewer'а.
pdftops - после чего все cross-refernces идут нафик. Это, грубо говоря, все равно, что напечатать документ, а потом его отсканировать. И потом - где ghostscript возьмет шрифт для печати документа, если в самом документе его нет? Подставит Courier?