Not sure if this would help at all, but I have heard from Altera that there will be a (very) BETA version of a new VIP Scaler in the UDX4.0 reference design that can be requested through your FAE. I don't know exactly when it will be made available, you can at least request it now.
I have a version of the new scaler and gave it a quick go through Quartus II 10.0 on the device you specified (on its own, not in full system) and it comes in just under 300Mhz. It is possible it could meet your frequency requirement in the full system and maybe allow you to rejoin your video stream earlier (scaling split images is annoying as you have to get the overlaps correct for each scaling ratio or the seam will look weird). If the chroma resampler, CSC and interlacer all run sufficiently quickly you could maybe get away with splitting the image with duplicators/clippers before the deinterlacer and rejoining with a mixer immediately after. You would still need your own frame buffer to run at the required speed, but you might not need to worry about syncing two halves of a frame through drop and repeat.
As a side note, the new scaler also supports 4:2:2 so if you were tight on memory bandwidth it could allow you to chroma resample earlier in the design and deinterlace, scale and frame buffer in 4:2:2.
Kieron