Leia sobre o hstore extensão. Em particular, você pode criar um hstore a partir de uma linha, o que significa que você pode fazer algo como:
changes := hstore(NEW) - hstore(OLD);
...pg_notify(... changes::text ...)
Isso é um pouco mais de informação do que você queria (inclui novos valores). Você pode usar
akeys(changed) se você quiser apenas as chaves. 
