But the elephant in the room is on-disk compatibility. There is absolutely no way that we can just change xmin/xmax to 64 bits without a disk format break. However, if we do something like what Heikki is suggesting, it's at least conceivable that we could convert incrementally (ie, if you find a page with the old header format, assume all tuples in it are part of epoch 0; and do not insert new tuples into it unless there is room to convert the header to new format ...
We could theoretically do similar thing with 64bit xmin/xmax though - detect page is in old format and convert all tuples there to 64bit xmin/xmax.
But I agree that we don't want to increase bloat per tuple as it's already too big.
but I'm not sure what we do about tuple deletion if the old page is totally full and we need to write an xmax that's past 4G).
If the page is too full we could move some data to different (or new) page.
For me bigger issue is that we'll still have to "refreeze" pages because if tuples are updated or deleted in different epoch than the one they were inserted in, the new version of tuple has to go to different page and the old page will have free space that can't be used by new tuples since the system is now in different epoch.
It is not so easy to move heap tuple to the different page. When table has indexes each tuple is referenced by index tuples as (blockNumber; offset). And we can't remove these references without vacuum. Thus, we would have to invent something like multipage HOT in order to move tuples between pages. And that seems to be a complicated kludge.