Parece que o recurso shuffle do pdftk fará isso. De man pdftk :
shuffle [<page ranges>]
Collates pages from input PDFs to create a new PDF. Works
like the cat operation except that it takes one page at a
time from each page range to assemble the output PDF.
O formato geral para um [<page range>] é dado como
<input PDF handle>[<begin page number>[-<end page number>[<qualifier>]]][<page rotation>]
em que qualifier pode ser even ou odd . Caso você deseje alternar páginas pares e ímpares do mesmo documento até que todas as páginas estejam esgotadas, é possível omitir os especificadores <input PDF handle> e <begin page number>-<end page number> , deixando apenas
pdftk infile.pdf shuffle even odd output outfile.pdf
em que infile.pdf é o arquivo cujas páginas devem ser trocadas e outfile.pdf é um nome para a saída.