1. Either be stored on the blockchain, or on a side-chain.
Must be on-chain, unless all bitcoin node also connected to side-chain network. Otherwise, the transaction would be invalid or can't be fully verified.
And then every name will be first come first serve, and to each address its identifier will be globally known for every node. This is probably what you want, but it's the hardest to implement because this needs either a hard fork, or you're basically going to need to convince a lot of nodes to start storing your side-chain of address names.
Yes and i already mention it needs hard-fork. It's not really best idea since it's just my random thought. It also have weakness, such as :
1. Bloating blockchain, even though transaction size is slightly slower
2. Make basic address validity check useless and more user will send to wrong address
3. Full nodes client require another DB/dataset just to store pair of bitcoin address and string
4. Grow incentives to sell linked private key for linked bitcoin address with good string
2. Or be from a 3rd party.
That would make Bitcoin decentralization useless
I'm not saying this is impossible, but for such a minor convenience, and in such a late stage of bitcoin, I don't think anyone really cares at this point.
That's what i think as well, most people even don't remember their own bank account number/id
![Roll Eyes](https://bitcointalk.org/Smileys/default/rolleyes.gif)