Lo único que se me ocurre es que separes cada página de cada pdf y luego los juntes mediante un script. Por ejemplo si tienes los pdf a.pdf y b.pdf, sacar a-1.pdf, a-2.pdf, etc, y lo mismo con el otro archivo, y después juntarlos en orden, a-1.pdf, b-1.pdf, a-2.pdf, b-2.pdf, etc.
Para juntar pdfs yo uso gs, ahora no recuerdo si sirve para separar también, me parece que sí.
