The following method is provided by notesofaprogrammer.blogspot.com, which first converts the PDF file to PS format, then embeds all the fonts while converting PS back to PDF:

pdf2ps example.pdf
ps2pdf \
       -dPDFSETTINGS=/prepress \
       -dSubsetFonts=true \
       -dEmbedAllFonts=true \
       -dMaxSubsetPct=100 \
       -dCompatibilityLevel=1.4 ./example.ps