Well, I didn't figure out how to do it with Mathematica, since I don't have any information about the internals in Mathematica which handle this, nor the time to hack it.
What I have done is :
Exported the mathematical typeset of my document from the notebook as a .png images.
(In fact, I found that taking a "ScreenShot" produced a better image than the SaveAs.)
Constructed the PDF body of my document with navigation index using Ruby/prawn, which allows me to import and position the
images of the mathematical typeset. This was a little bit tedious, but straightforward enough.
This is obviously not an ideal solution, since the rendering of the images slightly alters the appearance compared to the original, and any text in the image is not searchable, but that is a small price to pay to have the navigation in the PDF document.
Clearly, it would be better to do it all in Mathematica, or use another tool.
Purchasing an expensive package for occasional use is certainly not an option.