But how would someone know later which transaction is valid? Like, a new entrant to the network gets two transactions spending the same input, without a block c

But how would someone know later which transaction is valid? Like, a new entrant to the network gets two transactions spending the same input, without a block chain to determine ordering of transactions, this new entrant wouldn't know which was actually spent. Both transactions could have subsequent spends, so that is also not a way to determine which is the one to follow. You can't decide to follow neither, because it's possible (even likely) that the person who owns those coins now was not the person who tried double spending them.