May I suggest the PIC16F1824 (14-pin) or PIC16F1828 (20-pin) enhanced processors. Get the data sheet, these chips are awesome for what you're wanting to do! First, they include 4 ECCP channels, allow you to invert outputs, PLUS include a cool feature called Data Signal Modulator (DSM) that would allow you to embed your higher frequency within the slow clock, and even PWM that higher frequency while PWM the slow clock.

Hope this helps.
Mike