This reference I stumbled across says this about video generation on the Propeller:
Each cog has a hardware video generator and two special counters (CTRA and CTRB)
* Both counters have 3 special registers (CTR, FRQ, PHS)
* The basic function of the counter is to add the quantity in the FRQ register into the PHS register. When and how this is done is determined by the setting of the CTR register.
* Counters can operate independently from cog CPU with clock rates (controlled by CTR, FRQ registers) from 500 kHz to 128 MHz. This done via a PLL and VCO controlled by bit PHS(31).
* CTRA is used by the video generator, when the video generator is utilized.
This implies to me that you can clock your output scan rate independent of your CPU clock rate. Assuming that PLL applies a divisor or multiplier to the crystal input rate it seems to me the only thing you'll have to do is adjust whatever sample video generation code you're using so it applies a different multiplier to compensate for your "odd" synchronous clock input.
Frankly, the Propeller would be practically unworkable if it didn't allow something like this. For instance, the example code I've seen implies that it's possible to switch from, say, NTSC to PAL video timing simply by adjusting software. If the output scan rate was somehow synchronous to the CPU clock then it seems to me it would be necessary to change a crystal to do that. (VGA vs NTSC might be possible with the same crystal, as VGA is basically 2x NTSC, but PAL throws a monkey wrench in the works.) It also looks like it's fairly trivial to use the same counters to generate oddball frequencies for, say, driving LCDs. Unless I'm missing something it seems this should be a solvable problem.
I did suggest a shift register on the first page. ;^) If you're afraid of driving the propeller at a "strange clock" then a shift register should basically solve all your problems. According to my back of the envelope calculations you'll have to sample at *about* 2Mhz if you can grab parallel bytes instead of bits. Suddenly you can get a lot sloppier with your timing. (Ideally it would be nice if your shift register could generate an interrupt when it was time to clear it, but polling might work as well.)