How to structure an append-only database in PostgreSQL?
This sounds like a use-case for temporal tables. AFAIK PostgreSQL does not implement this natively. There are extensions for it. It can be written in user-code, usually with triggers.

The basic idea is that the data table has two date/time columns. These define the interval during which the value in a row is applicable - it is "the" value for that key during that interval. By key I mean natural key, not a surrogate row-labeling key i.e. the id column, not the key column in your example. It is best to make this a "closed-open" interval so the start time is included but the end time excluded. The resolution of the interval start and end columns has to be appropriate for the update frequency.

When a new value for that key arrives, the existing row is updated to set its end and a new row is written. The end date/time for the old row and the start date/time for the new row are equal, hence the closed-open formulation.

To use your example: the first row arrives

║ key ║ id ║ field1 ║ field2 ║ from                ║ to
║ 0   ║ 0  ║ a      ║ b      ║ 1970-01-01 00:00:01 ║ 9999-12-31 23:59:59 ║


Some time later the second row for this key arrives. The first row is updated, the second row is written

║ key ║ id ║ field1 ║ field2 ║ from                ║ to
║ 0   ║ 0  ║ a      ║ b      ║ 1970-01-01 00:00:01 ║ 1970-01-01 00:05:01 ║
║ 2   ║ 0  ║ a      ║ c      ║ 1970-01-01 00:05:01 ║ 9999-12-31 23:59:59 ║


To read a value 

select &lt;columns&gt;
from &lt;table&gt;
where id = 0
and from &lt;= &lt;right now&gt;
and to &gt; &lt;right now&gt;


The place holder &lt;right now&gt; represents the current instant on the server. It can be local, UTC or whatever. It just has to be consistent with what was used when the row was written. Using UTC uniformly makes this easier.

A consistent set of values can be read from the database from any point in history by using that historical time in the predicate instead of &lt;right now&gt;.

To delete a value set to to the current time.

There are, of course, downsides. Each table must have extra columns. These must be indexed. Ensuring intervals for each key do not overlap using only constraints is non-trivial. Every query must have temporal predicates and they must all use exactly the same time value.

These complexities can be mitigated by adding an archive table. When an existing row's to values is set, that row is also deleted from the data table inserted into the corresponding archive table. So each id value will only have one row in the data table, and many retired rows in the archive table. Queries no longer need the additional temporal predicates. Indexes (on the data table) need not include the interval columns. Historical queries become more complex, and every new value stored will incur the cost of an additional delete and insert.