I can think of perhaps one way of doing this but I'm not 100% sure (and I don't have actual code to share).
1.) Create and register two custom print templates with ArcGIS Server:
* One print template is your basic map, minus the legend
* Second print template has just your legend within the visible area of the layout (i.e. move the data frame off of the physical map space so it won't appear when you use the template).
2.) Use the 1st map template with PrintTask as you normally would.
3.) In the Callback function for the printTask, pass the results of the 1st printTask to a second function which generates the legend using the second print template.
4.) In the second printTask callback, initiate some sort of GP service using ArcPy to combine the two separate PDFs into the final, finished PDF.
Ugly, kludgy, and something I'd rather not tackle.
Steve