Is there any documentation or README explaining this whole 64-bit XID mechanism?
There is none, unfortunately. I would come back to this later.
Could you tell me what happens if new tuple with XID larger than xid_base + 0xFFFFFFFF is inserted into the page? Such new tuple is not allowed to be inserted into that page? Or xid_base and xids of all existing tuples in the page are increased? Also what happens if one of those xids (of existing tuples) cannot be changed because the tuple still can be seen by very-long-running transaction?
All this mechanism is around heap_insert/heap_update by calling heap_page_prepare_for_xid() and if it fails (due to tuple still visible) error is raised. Also If xid_base shift is not viable, it will try to remove old tuples.