Версию Postgres озвучь. Также, озвучь объёмы данных, среднюю нагрузку, средний прирост, сценарий использования базы (учет, отчетность, хранилище, аналитика).
Возможно, подойдёт вот такое .
В остальном - возможно варианты.
Варианты зависят от того, кто и как пользуется базой.
Список известных мне вариантов:
1. Захватывать изменения в триггере - я б так делать не стал.
2. Захватывать явно, на этапе модификации (как в приведенном примере, например) - этот вариант нравится больше всего, но доступен редко, т.к. потребует доработки приложения, использующего базу.
3. CDC - захватывать изменения в журнале транзакций, и записывать их где-то. Этот вариант хороший, но как легко и просто организовать Change Data Capture в PostgreSQL - не знаю.
Есть еще вариант 4 - хранить данные в таблице версионно, т.е. при обновлении строки сохранять старую версию и вставлять копию с обновлением как новую версию. Но для этого потребует серьёзная добработка вашего приложения.

Кроме того, в 9.4 появилась логическая репликация. Она может помочь с захватом изменений.
>>Понимаю, что штатных средств в postgesql для решения данной задачи нет (или я ошибаюсь).
Не ошибаешься. Штатных средств, в общем-то, нет нигде (Оракловый флешбэк - несовсем то).

Что до внешних ключей - зависит от того, какой вариант захвата и сохранения изменений ты выберешь.