The problem is not (ultimately) CGIs. It's HTTP. Any technology built on HTTP is going to run into the same issues. You're going to have to use some sort of kludge to get any sort of stateful information over HTTP, be it hidden input forms or cookies or whatever else. Asethetically, these are all awful solutions.
Replacing HTTP as an application platform would be wonderful. J2EE doesn't do that, and we shouldn't pretend that the handwaving it does is any less kludgy than solutions CGIs use.
----
Reinvent a rounder wheel.
Note: All code is untested, unless otherwise stated