I would take a look at how some of the ethernet works (sort of). You want to have a minimum and maximum timeout period. After master sends out query, each slave must wait a predetermine "random" timeout which is no less than the minimum and no more than the maximum. Whoever answers first gets first dibs at the channel. The other slaves must now re-start their timers and wait again. This is kind of expanding a bit on what Jerson mentioned.

As an example:
>Slaves are happily going along
>Master sends special command to re-assign IDs
>Slaves go into special "listening" mode
>>Slaves start random timer to request first ID
>>Slave response goes like this: wait for random timer
>>>If random timer expires look at TX line to make sure it's idle
>>>To simplify, you may add a "busy" line on a wired or configuration
>>>If line is idle, send simple acknowledge back
>>>Whoever "grabs" the line first, gets the first ID
>>First slave to respond creates a "busy" condition on the TX line (or the special "busy" line)
>>Any other slaves see this busy condition and must re-start their respective random timers
>>Any other slaves must also increment their IDs by 1
>Master re-starts its own timer to wait for next response
>Slaves keep self-assigning IDs until nobody else is left
>Master times-out and send special "back to normal" command
>Slaves go back to their happy lives

You could of course start adding more "intelligence" to this.