OpenVPN
precisa de acesso root porque precisa atribuir endereços IP à sua interface recém-criada.
Se você estiver executando em um modo gráfico, você pode tentar o NetworkManager
plugin para openvpn
, que roda muito bem e deixa sua vpn a apenas um clique de distância. Alguns usuários acham que NetworkManager
é um pouco intrusivo (mas isso é OFT).
Fora isso, sua melhor chance é, como você disse, sudo
. Muito melhor do que brincar com setuid bit, IMHO.