What you are suggesting is nigh impossible to do properly with standard tools.
As you noticed, saving the command history is usual will not work, since the file will be owned by the user, and they can can delete, clear or edit the file at will. Even if we could work around this, perhaps by making the command history file a pipe read by some trusted process, there's nothing to stop the user from just turning off the history file or pointing it somewhere else.
We could create a new shell with mandatory command logging to prevent that (with the logs sent to another process via a pipe, socket or syslog), but the user could still simply start a normal shell, or a Perl or Python interpreter among other things, to work around the logging. Logging what the subprocesses did, would require wrapping the whole session in
script or similar to log everything the user sees. Even then there is the possibility of just downloading code and running it, without printing it on the terminal. Preventing the user from running arbitrary programs would do it, but it would also prevent doing most useful things. Preventing running shells or Perl scripts would also prevent many common tools from working.
This result isn't surprising, considering that the shell and other utilities are meant as a tool for the user, not against them.
Perhaps you could arrange the user's session to be wrapped in
strace or similar to see every interaction their processes had with the system, but reading the
strace log from a longish session would not be much fun.
Also, I would think your users would object to this level of monitoring, I know I would.