Se você quiser executar o comando através da url do arquivo, exemplo http://exemplo.com/teste.php e nesse teste.php tem seu shell_exec, você precisa certificar-se que o Apache tem permissão para executar esse comando.
Para dar a permissão ao Apache basta saber o usuário, isso vai depender da distribuição do Linux que esteja utilizando. Se você estiver utilizando CentOS será Apache mesmo, caso esteja utilizando Ubuntu será www-data.
Após saber disso verifique qual o caminho do arquivo onde estão os arquivos que você quer executar a permissão sudo pelo Apache, ai você edita o sudoers
vim /etc/sudoers
e adicione a seguinte linha.
apache ALL=(root) NOPASSWD: /caminho/da/sua/pasta
ou
www-data ALL=(root) NOPASSWD: /caminho/da/sua/pasta
Basicamente você estará dizendo ao servidor que seu Apache tem permissão para executar os arquivos dessa pasta como root.