Well heres my thoughts:

If writing to a pin will cause too much delay, then software PWM is out anyway I think. I may be wrong, but it seems to me that is like a pause. What I mean is program waits for the pwm to finish before going further.

I am not sure of the above, someone PLEASE correct me if I am wrong!!

you say you want 100 to 125 Hz. Does that mean you can tolorate variation between the 2? ie: 112 Hz plus or minus 12 Hz?

You can get twice as much time to do things if you run the pic at 8MHz. Double the instructions executed in the same time.

Use timer 2 with a prescale set to 16, tmr2 output would then be 500K (@8Mhz). set the postscale to 16 and you will get a flag at 122Hz on TMR2IF with PR set to 255.

Just poll TMR2if in your main if you don't want to use interupts.

You haven't given any info as for the resolution you want for the duty cycle but I think you can play with PR to get your duty cycle. but I need to think about that some more.