Os documentos estão desatualizados / enganosos.
O ! deve ir antes de --destination , não depois dele. Experimente:
-A OUTPUT ! --destination 127.0.0.1 -m state --state NEW -j LOG --log-prefix "new_connection " --log-level 7
A pista é a linha de resumo na página de manual :
[!] -d, --destination address[/mask][,...]