Solução
nmcli --fields UUID,TIMESTAMP-REAL con list | grep never | awk '{print $1}' | while read line; do nmcli con delete uuid $line; done
No Ubuntu mais recente (15.10) use este comando:
nmcli --fields UUID,TIMESTAMP-REAL con show | grep never | awk '{print $1}' | while read line; do nmcli con delete uuid $line; done
Também será possível usar o campo TIMESTAMP para saber quantos dias / mês são passados da última conexão, como por exemplo, queremos remover a conexão com mais de 1 ano