MVCC for updates is DELETE followed by INSERT. That is what the docs are talking about when mentioning "new rows", not the type of "new row" that is done with an INSERT statement which is ALWAYS appended to end of table. I actually had to ask about this one in PostgreSQL slack chat because I wasn't 100% positive that index clustering order does not influence INSERT location, but apparently even clustering order does not influence a location for INSERTs other than the end of the table.
My (admittedly inexperienced) reading of the code (src/backend/access/head/hio.c::RelationGetBufferForTuple) leads me to conclude that my assumption about the behavior is indeed correct. Both update-related insertions and isolated insertions result in the system using the free space map (FSM) to locate existing pages with free space on them to use for persisting the newly created tuples.
Specifically:
/*
* We first try to put the tuple on the same page we last inserted a tuple
* on, as cached in the BulkInsertState or relcache entry. If that
* doesn't work, we ask the Free Space Map to locate a suitable page.
* Since the FSM's info might be out of date, we have to be prepared to
* loop around and retry multiple times. (To insure this isn't an infinite
* loop, we must update the FSM with the correct amount of free space on
* each page that proves not to be suitable.) If the FSM has no record of
* a page with enough free space, we give up and extend the relation.
*
* When use_fsm is false, we either put the tuple onto the existing target
* page or extend the relation.
*/
and
if (targetBlock == InvalidBlockNumber && use_fsm)
{
/*
* We have no cached target page, so ask the FSM for an initial
* target.
*/
targetBlock = GetPageWithFreeSpace(relation, len + saveFreeSpace);
