is there a better way, preferably without an extra software-stack, to lock specific ssh users into a program without access to a working shell? Imagine a cli program which should be the only interface a user has access to via ssh.

My hacky solution:

In /etc/passwd replacing the user-shell with following script:

#!/bin/bash
/bin/bash -c /usr/bin/cli
exit 1

Issue at Hand

You desire to lock remote users into using a specific shell when they connect to your server. As you have probably found out, chsh or other solutions are geared towards local users.

Solution

As per this solution by user muru, I would edit your sshd_config to use the ForceCommand option.

You could use a ForceCommand along with Match:

 Match Address 10.1.0.0/16
 ForceCommand /usr/bin/[some shell]

From man sshd_config:

Match Introduces a conditional block. ...

The arguments to Match are one or more criteria-pattern pairs or
the single token All which matches all criteria. The available
criteria are User, Group, Host, LocalAddress, LocalPort, and
Address.

ForceCommand

Forces the execution of the command specified by ForceCommand,
ignoring any command supplied by the client and ~/.ssh/rc if
present. The command is invoked by using the user's login shell
with the -c option.

So, the command you specify would be executed using the user's login shell, which must accept the -c option. The connection is closed when the command exits, so for all practical purposes, that command is their shell.

Using ForceCommand in your configuration file you can force the use of a shell that supports the -c option. I would also reference this serverfault post to get more information on how to complete this task.

Conclusion

Use your sshd_config options to force the use of a shell that can support -c as that will close the shell and session once complete.

Please comment if you have any questions or issues with this answer. I appreciate feedback to correct any misconceptions and to improve my posts. I can update my answer as needed.

Best of Luck!

You would be better suited to create an actual BSD jail or chroot environment for the user in question. Of course that would require some manual creation of a user, group, mini linux file system, acquiring the libraries necessary for cli etc or using the jail tools available in unix distributions.

See the documents for more information

Linux chroot

BSD jail