In several of my designs (non-pic mind you), I switch between two clocks
routinely.  One is used for what might be considered similar to JTAG, and
the other is standard run mode.  Just mux between them.  But, you should
probably have some sort of routine that it drops into when you switch, that
would allow the clocks to settle before going back to execute the code.
Some devices will switch with no delay between them, some will have some
settle jitter, so it depends on what you choose to mux.  I've used IDT 805
parts with pretty good success.

Cypress also makes a programmable clock, with dual outputs and can switch
(supposedly, I don't use it in that mode) between both frequencies.

Now...for the bottom line, are you trying to cut down on power consumption?
By adding an external device to swap clocks, and dual clocks (or divider for
one master), may take just as much power as to run a chip at a higher clock
all the time.