Next-generation wireless networks are going to have highly dense, small cell structure with a large number of femtocells. The dense deployment of the femtocell network architecture is expected to meet the growing data demand by leveraging millimeter-wave structure of 5G wireless networks. However, arbitrary deployment of large number of femtocells underlying a macrocell will pose a challenge for collision and confusion-free Physical Cell ID (PCID) assignments as the total number of available PCIDs is limited to 504. In this paper we propose a distributed, randomized k-clustering algorithm for collision and confusion-free PCID assignment problem, which is known to be NP-complete. To reduce the total control message flow, we create overlapping clusters in ultra-dense femtocellular networks, where each cluster head runs the distributed randomized PCID allocation algorithm and locally monitors the conflicts to avoid the collision and confusion constraints. We prove the correctness of our proposed algorithm and analyze its time and message complexity. Through simulation experiments, we also show the effect of different parameters on the PCID allocation objectives.