Is it possible to audit a Postgresql 9.4.5 database in such way that I could find when a specific record was deleted? I don’t know what do I need to have enabled / available for such
No, it is not. Data that is gone is gone. This type of auditing is normally implemented by custom code (triggers writing to an audit table or something like this).