You can use Inkscape for this.
File -> Open -> open your PDF.
A dialog "PDF Import Settings" will pop up. If you tick the checkbox "Import via Poppler", the text will be converted to symbols on importing.
If needed, you can convert symbols further to paths and edit them (but as far as the specific question here goes, namely editing/sharing the pdf without relying on the fonts, symbols work fine).
A few years late, but considering I'm having this issue and this was the initial post to pop up on my searches, I figured why not.
I, and others, have this issue. It's apparently been around for awhile. evince doesn't render some of the fonts appropriately.
You can check to see if the fonts are embedded within your pdf document and then fix it with ghostscript.
I found an article on stackoverflow that explains it in pretty good detail. It's enough to work off of. Most of the fonts are most likely in your system already (they were installed on my system).
I also happened to find a slackware tutorial post that went in to similar detail.
Technically, and ultimately, though, its just how evince renders the pdf file. I can load my pdf files using different apps and I've noticed each one renders in a unique way.
The only one I've come across that renders it properly is Adobe's Acrobat Reader. I've tested this on multiple systems and devices using all sorts of pdf apps from OSS to Proprietary.
I still use evince regardless and sadly I don't have the time right now to play with the source to figure out why this happens. Maybe I, or some one else, will fix it one day. You never know. It is OSS.
Best Answer
This might not be the most relevant question for askubuntu, but I'll try to answer it nevertheless: You probably included graphics in your document that use the Helvetica font (a common example are the axis labels for figures created by Matlab), right? If you used Helvetica in your document (e.g. with
\usepackage{helvet}), the Helvetica replacement Nimbus Sans L would be used instead.Embedding the fonts from external figures is not possible at the moment (it should work if you make sure that the external figures embed the fonts themselves, though!).
Therefore, as suggested in the comments, the only solution seems to be to do a PDF->PS->PDF conversion, e.g.:
Unfortunately, hyperlinks for example will not survive this transformation.
See this question on the (more relevant) tex.stackexchange sister site: https://tex.stackexchange.com/questions/10391/how-to-embed-fonts-at-compile-time-with-pdflatex