Sim, setuid bit deve funcionar bem (a menos que haja alguma proteção no nmap que não permita que ele seja executado com bit setuid ativado , mas eu não penso assim).
Outra opção possível (e, na minha opinião, muito melhor) é configurar o sudo para permitir que determinados usuários executem o nmap com alguma configuração similar em / etc / sudoers :
username ALL = NOPASSWD: /usr/bin/nmap