I still do not see that you can avoid collisions, even with your random back-off idea. You have no garantee without some external control/arbitration. My first response is to do it the simple way with EPROM'd addresses, but I also see that that does not facilitate adding of devices in an easy manner.
And,, I get the impression that you are trying to learn from doing it the hard way (most commendable).
If you do get it to work, I, for one, would be interrested in how you went about it ( I don't want to see your code, I just want to hear you explain the logic that made it work). Good Luck. I hope to see notice of your success.