Before addressing your specific question I would offer the idea that your team carefully weigh the cost tradeoff of trying to shove a square peg into a round hole vs. changing to a properly shaped hole (like a fancy new Stratix IV FPGA).
Also before immediately jumping to the idea of splitting the video into two seperate paths, you may want to put more time into getting the design to meet your timing requirements via design partitioning, incremental compilation, logiclocking, etc.).
At the end of the day it's all money so you guys just need to decide how/where you want to spend the time and money.
Now, let's assume you've settled on splitting the video into two paths. You can add run-time control to the frame buffers to help control when they change between frames.
You could also write your own frame buffer that handles two streams and locks them together (that would be my choice).
Jake