Usando o LaTeX!
0) Instale o LaTeX se necessário
1) No seguinte documento de látex, substitua x.pdf pelo seu file.pdf
\documentclass{article}
\RequirePackage[a4paper,top=3cm,left=3cm,right=3cm,bottom=3cm]{geometry}
\usepackage{pdfpages}
\usepackage{fancyhdr}
\begin{document}
\fancyfoot[RO]{Braga}
\fancyfoot[LO]{2015}
\fancyfoot[CO]{===}
\fancyhead[LO]{Lecture notes of askubuntu}
\fancyhead[RO]{\thepage}
\includepdf[pagecommand={\thispagestyle{empty}},pages=1 ]{x.pdf}
\includepdf[pagecommand={\thispagestyle{fancy}},pages=2-]{x.pdf}
\end{document}
3) execute pdflatex addfooter.tex e um addfooter.pdf será criado.
4) adapte os cabeçalhos, rodapé (esquerda, centro, direita), ajuste os tamanhos das margens, etc.
Atualização:
Embora a versão LaTeX nos dê mais controle sobre os detalhes,
como @steeldriver, apontou,
Em algumas situações, uma linha de comando pdfjam é a melhor escolha. Uso típico:
pdfjam --outfile newfile.pdf --pagecommand '{}' oldfile.pdf