Without patching existing shells and avoiding process accounting on your system, your only recourse is to write yourself your own shell. The security issues involved with this make this solution impractical, so I'm afraid I have no advice for you aside from that already given. Consider that if you write your own shell, you're going to have to find some way to selectively grant access to other shells on your system, so that shell scripts can run, but interactive sessions cannot be started (thus allowing the users to execute commands via the other shell, avoiding your logging). This is non-trivial. Your best solution is to take advantage of process accounting.

Any mechanism like this is going to be inherently platform-specific. If this is a Unix system, contact your system administrator for information on configuring your system to enable process accounting, assuming it isn't already enabled. This is something that occurs at a relatively low level in Unix (but is supported essentially the same across a variety of Unix types), which is where it needs to be, since shells provide control to the system at such a high level, they can be easily tricked or circumvented, given that a lot of programs trust shells and have ways of allowing the user to drop to one.