Apply PhD with no recommendation
If you can be open with your formal supervisor about the "personal problem" s/he has with you, you could simply ask, "I am interested in pursuing a PhD. I know that we have disagreed about XYZ and so I wanted to ask you if you believe you could write me a fair recommendation."

Note, that this is still risky - the supervisor can write a bland recommendation (which holds little weight) or agree to write it and write a bad one anyway. 

What about the director of the program you attended? That could be weighed more favorably. Other faculty members? My PhD dissertation chair never wrote recommendations for anyone, so I never even asked him (we never had a falling out or anything, it was just his personal policy). It never hurt my chances of jobs or other things because I had other faculty and references write litters for me instead. 

Good luck!