Yes it can, but might require some clever coding to meet the timing requirements at 1080p.
Hardware timers can be used to trigger from Hsync and Vsync signals to provide an accurate interrupt call at the time the correct location is being drawn to the screen, this might then trigger a DMA transfer that shovels a large RAM array into a GPIO port where you connect your MUX signal and OSD color signals. Perhaps using 8bits on the GPIO port to have 1bit MUX signal, 2bit red, 3bit green, 2bit blue. The speed of the DMA could be tuned to make 1 transfer for every 4 pixels drawn to make fat long pixels and the DMA could be triggered to pump out the same array 4 times in a row to make 4x4 sized OSD pixels on the screen.
While the DMA is pumping out pixels this gives the CPU 4 video lines worth of time to fill up another array in RAM with the data for the next set of lines. Once the 4 lines are done the DMAs source address is then switched to the new array location to pump out the new pixels while the CPU starts preparing the next one, this repeats until the whole video frame is over and once vertical blanking starts the CPU now has a few microseconds of time to do anything else it needs to do, like perhaps user interface stuff, once a new video frame starts being drawn it all repeats again.
How much resolution and color depth you can afford depends on how well the code is optimized and how fast the CPU is. Maybe you need huge 16x16 sized pixels to have enough CPU time to do it. Or maybe you optimize the hell out of it and use the SPI bus running at 130MHz to get high speed output and get 1x1 sized pixels but only in a single color. Depends on what you optimize for.
Another trick that might be possible is to get a very powerful MCU that is capable of outputting 1080p video on a 24bit RGB bus. This bus is designed to connect a LCD to it, but with some hardware interrupt and register twiddling trickery you can perhaps synchronize the start of the frame on this video output bus with the start of frame on VGA. In that case you can overlay a high resolution 24bit color 1920x1080 picture over the original video by simply using MUXing between the video coming from the MCU and from VGA by using one of the color bits as the "transparency flag" to switch the mux at the right moment. Tho chips that can output 1080p video tend to also run Linux