It is 100% possible. For ttys/ptys (text mode), the easiest way is to add a shim to /bin/{ba,da,a}sh (e.g., a second .code segment, R-X) and change the entry point (much as an ELF virus would). Barring access to that in this case, one can modify ~/.profile or ~/.bashrc (etc.) to, as a very simple hypothetical model:
exec ~/.malicious_programme
which may load dynamic shared object code to hide the malicious programme in question (example: allow .profile read and modification, but hide the line. And/or hide the programme.)
One may then use the UNIX98 pty(7) system or even simply pipe(2) to record all input in a forked shell, assuming the fd is not marked FD_CLOEXEC, and even change user input to the shell.
In X11, although kdm/gdm/xdm run as setuid root (or the equivalent in capabilities [see setcap(8)] or whatever security model you're using if non-default), things become more complicated, obviously. If one can elevate privileges? iopl(2) or ioperm(2) makes life quite easy with direct access to 0x60 / 0x64 keyboard ports on x86. Since we're assuming you can't, we must look for an alternative route. I know of several, but I am not entirely sure you want a dissertation on how it's possible and the interfaces involved.
Suffice to say, ring 3, non-superuser trojans are quite possible on *nix, in spite of process isolation, as a result of various issues (particularly with X) that has added features for user-mode daemons to provide, e.g., text-to-speech support for all apps w/o compromising the system's security. I already outlined one that works analogously to ttysnoops (which is long past its expiry date), and it does not require root. I have sample code for this case (which would include inside terminals in X), but I have not as-yet published it. If you want more information, please feel free to contact me.