Pursuing documents for arcpy.mapping, I see that you are not joking about the "restriction".
Instead of adding new pages, have you considered adding bookmarks to PDF?
And the only Python software I could dig that could add bookmarks was pdfrecylce . It is in version 0.05, so I'm going to step on a limb and guess that it may not be too stable.
If you are ready to use Java or C #, there are iText and iTextSharp (but I'm biased). There are many other PDF libraries floating around that can manipulate existing PDF files ... select a language and start a Google search.
source
share