Monte-Carlo algorithm for clustering
I suspect this clustering algorithm is going to give a poor quality clustering.  The cluster heads are chosen just about arbitrarily (randomly, essentially) and then points are assigned to a cluster if they are near a cluster head or near some other randomly chosen points in the cluster.  The whole algorithm looks unprincipled and I have serious doubts about the quality of the clustering it will produce.

Of course, if the clustering is of low quality, then it just doesn't matter what the running time is.  I can suggest an extremely fast algorithm if you don't care about the quality of its output....

As far as running time, it will depend upon the distribution of the input points.  If the input points are distributed uniformly across the input space, then I would expect that each iteration of the inner loop will remove roughly a $0.15^d$ fraction of the input points.  This suggests that you'll need to do about $1/0.15^d \approx 2^{2.7 d}$ iterations.  Each iteration takes about $O(n)$ distance computations, and each distance computation takes $O(d)$ steps, so I'd expect the running time to be something like $O(n d 2^{2.7d})$.  That's dominated by the exponential factor, so the worst-case running time estimate is very bad, in high dimensions (e.g., $d \approx 100$).  Welcome to the curse of dimensionality.

This algorithm does not look promising to me.  Of course, before drawing any serious conclusions, you'd need to do a serious evaluation of both its running time and the quality of its clustering, on relevant input distributions, as compared to other standard clustering algorithms.  So, if you want to seriously pursue this direction, you need to start studying the state of the art and work on performing such a careful evaluation.  But personally, I think your time would be better spent by starting to look at what's available in the literature and seeing if you can make any standard algorithm work for your application.