FPGA with SDRAM frame buffer and some analog devices TV decoder, and another analog devices triple RGB DAC for VGA.
That's technically the best way to do it. For even better results, use a plain ADC instead of a video decoder (so you can implement an adaptive decoder inside the FPGA) and use HDMI out instead of VGA. And if you want it to work at all, you'll really need a Tiffany Yep level of knowledge about DSPs and digital design.
You might be able to use a raspberry pi + usb composite capture device + usb VGA capture device for under $300
I remember reading that the USB controller in the Raspberry Pi is quite limited and would probably have problems keeping up with video input and output at the same time. If you ditch the VGA output and use built in HDMI, it would probably work fine and be a surprisingly effective way to do it.
On a $300 budget, you're probably best off buying a DVD recorder with component (easily converted to VGA) or HDMI output and using it only for the video conversion. You might even be able to find one for cheap where the actual DVD drive has failed but everything else still works. Or for a more direct solution, just buy a monitor that has composite input.