I think providing you switched to an ITX board, fitting the components wouldn't be to much of an issue you'd probably have to use a PCIe cable to mount the card to an edge or the top somewhere, and you'd probably want an exhaust type GPU so you could duct air into it from outside through a vent somewhere and it could exhaust out of the system.
The difficulty is always going to be powering it. If you put any GPU in, an external brick type PSU just isn't going to cut it, you're going to need a proper PSU. Any idea of the internal dimensions of a NES, could you squeeze an SFX PSU in there perhaps?