Software-generated video is definitely difficult to get working from scratch, limited in resolution, and expensive in CPU cycles, but it's been done on several microcontroller families [1] [2] [3]. You generally still need an external resistor network to do the D/A conversion, though.

[1] http://www.rickard.gunee.com/projects/video/sx/gamesys.php

[2] http://www.theresistornetwork.com/2013/03/avr-vga-generation...

[3] https://hackaday.io/project/8537-vga-blinking-lights