I am worried that will require CREATE INDEX to wait for a long time.
Not unless there are long running transactions. We are not waiting for the lock, but only for the current transactions to finish.
Is the pg_index xid idea too complex? It seems to give you the per-tuple index bit, without the restrictions.
How do we handle HEAP_ONLY tuple cleanup ? If I understood the proposal correctly, at the end of the create index, a HEAP_ONLY tuple may have pointer from the new index, isn't it ?