The specs for the Propeller microcontroller say "External Clock Speed: DC to 80 MHz ". That sort of implies you could lock onto an external oscillator. (The specs also say there's an on-chip PLL which can multiply the external clock by 1-16x, although enabling it limits maximum input clock to 8Mhz... although that may not be a problem. It sort of looks like the "standard" config for Propeller demo boards is a 5Mhz input clock. That times the 16x PLL multiplier results in the quoted "80Mhz" speed.)
According to this page, the 15.6672 MHz clock is the Mac Plus' pixel clock, which means that the RAM in the Mac needs to supply one monochrome pixel every .064 microseconds. Assuming you're working with 8 bit bytes that means something generating a screen like the Mac Plus is going to need to run at a little less then 2Mhz, as long as you have a shift register doing the pixels. So... my ignorant suggestion would be to tap the 7.8336 Mhz clock being supplied to the Mac Plus CPU and set your multiplier PLL to 8x, giving you a core speed of almost 64Mhz and thus lots of CPU time to play with the incoming monochrome bits. The only thing you'll need clocked at 15.6672 Mhz is the 8 bit serial-in/parallel-out shift register you'll read every four external clock cycles. (Fairchild MM74HC164, maybe?)
The thing that sort of worries me is that a standard Propeller has 32K of "hub ram" and a 512x342x1 display will take up about 22K of it, which rules out "double buffering" the input and the output. (IE, you're going to need a cog filling up that buffer at the Mac's input speed at the same time you have a cog(s) reading it and making a VGA display out of it. Maybe you could offset things by half a screen width or something to keep them from running into each other.) Timing is also going to be a problem because your clock speed is going to be "unusual", thus any sample VGA code you might borrow from is going to have to be adjusted. (This may not be a huge deal if you're driving a nice forgiving multiscan monitor, but it's something to keep in mind.)
Of course, I'm an idiot when it comes to electronics so take all these suggestions with a Borg Cube's worth of salt.