Is there any way to directly manipulate a PDF file with Type 3 embedded fonts (yes, those PDF generated from old tex/dvips and CM fonts), and replace them by decent Type 1 fonts? I know that once printed they should look ok, but I'm using a Kindle to read them and they look hideous.
On the off chance that you have at least the Postscript file used to generate the PDF, Heiko Oberdiek's pkfix is likely to do the job. The man page for pkfix-helper gives some useful hints and a workaround for the application of the utility.
If you really have to work with the PDF, then you have a problem, one that is not insoluble, but I think you will have to do most of the work yourself. Type 3 fonts carry very little metadata, and what little metadata they have are probably lost in the translation to PDF. To recover the original information, you have to infer information about the glyphs, their placements and their font geometry. This is in principle an easier task than OCR, but it's a problem fewer people want to solve so there is next to nothing in the way of ready-made applications, at least that I know of. The technology is explained in several places, e.g., in Mao, Rosenfeld & Kanungo (2003)'s survey Document structure analysis algorithms: a literature survey, and I think Ocropus and iText provide a good infrastructure to build a solution. But this is so much unspecified work that I think it does not count as an answer.
There is an open source application called PDFedit, that I've only used briefly. http://pdfedit.cz/en/index.html
Perhaps you can change the fonts there?