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.