Uhm... Potresti crearti un gruppo "shell" ed aggiungerci gli utenti che hanno il permesso di usare una shell...
Quindi le shell (/bin/bhash, /bin/sh, /..., /...) le dai al gruppo shell:
chgrp $SHELLS shell
E poi levi tutti i permessi ad Other e li lasci a Users e Group...


Se pero' qualcuno volesse eseguire dei programmi nessuno potrebbe impedirglielo: basta che scrivono un programma in un linguaggio che puo' fare cio' che fa la shell (ad esempio il C)...
Potresti levargli anche il permesso di usare il gcc (e tutti gli altri compilatori/interpreti), ma volendo potrebbero pur sempre scaricare un pacchetto di binari del gcc da internet ed usarlo... (oppure scaricare ed usare un programma in grado di fare cio' che non vuoi che venga fatto)

Penso che l'unica a questo punto diventi impedire a tali utenti di usare tutte le shells,interpreti,compilatori (come ti ho suggerito prima) e negare il permesso di esecuzione nelle directory nelle quale possono accedere (la home, e /tmp)...
Cosi' *credo* che diventerebbero immuni