Solution 1:

You can export PDFs from InDesign with the fonts embedded, but that's assuming you have the fonts on your computer and can direct the program to those font files. I'd imagine Acrobat Pro supports this too. I'm not sure about editing the fonts in a PDF file that's already been generated, but if there's any tool that will let you do it, it's probably Acrobat Pro (not to be confused with Acrobat Reader).

Solution 2:

Ghostscript can do that. One condition though: the font(s) referenced by the original PDF need to be present on the system where you run Ghostscript.

Here is an example command to run on Windows:

gswin32c.exe ^
  -sFONTPATH=c:/windows/fonts;d:/some/dir/with/more/fonts ^ 
  -dCompatibilityLevel=1.4 ^
  -dPDFSETTINGS=/prepress ^
  -dCompressFonts=true ^
  -dSubsetFonts=true ^
  -dNOPAUSE ^
  -dBATCH ^
  -sDEVICE=pdfwrite ^
  -sOutputFile=output.pdf ^
  -c ".setpdfwrite <</NeverEmbed [ ]>> setdistillerparams" ^
  -f input.pdf

The resulting output.pdf should have all fonts embedded which input.pdf didn't have. Just make sure that -sFONTPATH=... contains (at least) one directory where the missing fonts are found by the gswin32c command.