You might want to have a look at HOT [0] tuples if you haven't already.
[0] - https://www.cybertec-postgresql.com/en/hot-updates-in-postgr...
Eventually maybe PostgreSQL will get a second storage engine that uses an undo log instead, like the somewhat stalled zheap effort for instance.
That said the numbers of rows you are talking about are easy peasy for PostgreSQL.