After much research , I found a tool that works on Linux.
It's free to try but I think it needs a 50$ license. I was able to use it to add a margin to my pdf and preserve the outline.
I have not been able to find a free tool. If someone does find one, please feel free to post an additional answer and I'd be happy to try it out.
If of help to anyone stumbling into the same problem, the tool I've used is Master pdf editor:
Document -> Page Layout -> 'width'.
(On RHEL/Fedora I had to install qt5-qtsvg library to get it to work.).
 Linux tools I've tried:
(as per https://www.tecmint.com/best-pdf-page-cropping-tools-for-linux/)
- Briss - can't expand margin, only shrink.
- pdfcrop - can expand, but looses table of content (as described by question).
- Pdf Shuffler - doesn't crop, only re-arrange/delete pages.
- Evince/Okular - Don't seem to have the ability to edit page layout/crop.
- pdf-quench - couldn't get it to work.
- KCrop - Can make a page smaller, but not bigger.