On a Windows machine with a virtual pdf printer (in my case the one that comes with Adobe Acrobat Pro) I can print to a pdf file and the fonts get embedded.
I tried this a few years ago (before there was export_fig). The biggest problem I had, and the one that made me give up, was I couldn't bypass the print dialog box. I always had to provide confirmation. I think there may have also been small changes in the figure and in some cases sections of the figure were replaced with bitmaps.
I can get a little closer. On both Windows and Arch Linux I have a virtual PDF printer installed and named PDF Printer. On Windows it the Adobe Acrobat Pro (or maybe Adobe Distiller printer) on Linux it is the CUPS-PDF printer. On both systems
print '-PPDF Printer' myfilename.pdf
gives the desired result without any user interaction. I think it should be pretty OS independent and consistent across PDF printer type. Integrating it into export_fig may be harder. You will either need the user to supply the name of the PDF printer or a good guess as to what it is called. Guessing the printer name will probably be harder than guessing where Ghost Script is installed.