Label Assignment Problem
I dont know the solution of your problem: especially as we dont have a limit on the ID's. My "guessing" is that you cannot solve this problem with complexities you listed. 

I will only answer your following question:

Does the usage of randomized leader election is eligible in the case of graph as described above?

I dont suggest using leader election. Its lower bound does not meet your requirement (it is still an open problem to solve the election problem with $O(D)$ time and $O(m + n \log n)$ message, Peleg 199*). The known randomized election algorithms so far do not work on arbitrary graphs. There is a new algorithm that runs in arbitrary graphs (but requires knowledge of $n$). This algorithm is not yet officially published (due to Peleg et al. 2012).  

I will list the references later.