I faced a similar task in the past. My solution was to write a script heavily using pdftk toolkit, in my case on Linux (pdftk is included in most full-fledged distributions).
The solution in your case would be to first split the two documents into separate pdfs one per page and subsequently merge them into a single one.
I guess, with some command line literacy, looking at the examples should be enough to come up with your solution. Alternatively, if this is a one-time job and you really are after a GUI-based solution, you can split the document into separate pages using your favorite PDF viewer and simply print each page into a separate pdf file on your disk. Subsequently you could concatenate the files back again using a tool such as e.g., PDFedit.