Você pode usar cnetworkmanager
para isso.
Editar:
Após algumas investigações, fica claro que é impossível executar dois "provedores de configuração de usuário" (um aplicativo escutando em um determinado endereço dbus) ao mesmo tempo, e o cnetworkmanager precisa agir como tal "provedor de configuração" (em menos até que a conexão esteja configurada).
Agora, o que você pode fazer é adicionar as informações para a conexão ao gconf sob a chave /system/networking/connections
(você pode fazer isso a partir da linha de comando ou de um script) e usar dbus ou uma ferramenta de linha de comando como cnetworkmanager ou nmcli para se conectar a ele. Talvez você também tenha que adicionar a chave ao chaveiro do usuário primeiro (para evitar popups de senha).
Mas é claro que isso não funcionará em uma área de trabalho que use outro cliente NM do que o nm-applet (por exemplo, o KDE). Você teria que descobrir como fornecer uma configuração para eles também ...
Editar 2:
Parece possível através de org.freedesktop.NetworkManagerUserSettings
no sistema DBus, mas isso é tudo mal documentado IMO ...
Você pode querer ler sobre as configurações e sobre o Especificação da interface DBus .
E aqui está um exemplo relevante (talvez você deseja configurar uma conexão de usuário em vez de uma conexão de sistema)