A teaching shell might be more important. Something like what Reason does for OCaml, but done for the the unix command line.
Use the model of something like is common with a lot of MUD clients, all text input occurs in a field at the bottom (look at tinyfugue).
Below that have a set of autocomplete hints. This would be filled in based off of common usage, and knowledge of binaries avialable in the path, knowledge of the command line arguments of common tools (git-prompt.sh is really nice for getting my new-to-git coworkers started, for instance).
This could be wrapped up in the terminal, but needs to be aware of the environment in which it's being executed which moves beyond the purview of most terminal emulators and into the area of the shell itself.
EDIT: Rough ascii art illustration:
+----------------------------------------------------+
| > cat foo.txt |
| Hello, world! |
| |
////////////////////////////////////////////////////
| |
+----------------------------------------------------+
| > ca |
+----------------------------------------------------+
|cat | cac... | cal...| can... | can... | cap... |
+----------------------------------------------------+
`cat` first because of frequency of use (in general) and recent use. Others are showing other matches of the currently typed value + one letter, ... indicating more than one option.
You'd want usage statistics on common commands, and you'd need to assemble a database of command line options. Might be able to grab these from man/info pages, but formatting is likely inconsistent. Could at least get started that way. And you'd want to collect the users history to customize it. This'd be equivalent to the hints on many mobile OS keyboards.
I could see this being pulled into the terminal, rather than the shell itself. But it'd still need information about the underlying environment (easy if local, hard if remote).
How do terminal emulators on tablets handle keyboard input? Do any of them offer guided hints?