Erstmal zu den Ausgängen:
Wenn sich die Funktion der Outputs auf des Schalten von LEDs reduziert, würde ich zum Einsatz von von sowas raten, falls die Bauform ok ist: http://www.ebay.de/itm/20-Stueck-WS2812-RGB-SMD-5050-PLCC6-LED-mit-integriertem-WS2811-Controller-/350765334356
Dann kannst Du mit einer Datenleitung mehrere hundert RGB LEDs in Helligkeit und Farbe steuern...
Anzeige: I2C LCD oder GLCD
Ein Mega2560 hat 53 I/O Pins.
Mit 2 Stück davon, welche seriell miteinander sprechen, sollte Dein Projekt machbar sein, wenn der "Bildschirm" im Rahmen bleibt.
Programmiert wird in C.
Grüße
Helmuth
edit: Alternativ ein I2C Port Expander.