Suppose a Cohen is dating a Jewish girl, and both parties have had relations with non-Jewish people. Normally, a woman who's had relations with non-Jews is forbidden to a Cohen. Does the fact that he had relations also with non-Jewish people remove his Cohen sanctity and permit them to each other or can they not get married?
The answer is that a Cohen who has relations with a non-Jewish woman is not removed from his sanctity and therefore not permitted to marry a woman who's had relations with non-Jews.
איזו היא חללה: זו שנולדה מאיסורי כהונה; וכן אחת מן הנשים האסורות לכהונה שנבעלה לכוהן, נתחללה. אבל הכוהן עצמו שעבר העבירה, לא נתחלל.
What is meant by a challalah? [A woman] born from [relations] forbidden to the priesthood.1 Similarly, any woman who is forbidden to the priesthood who engaged in relations with a priest becomes a challalah. A priest who commits a transgression himself, however, is not deemed a challal.
I do believe that the accepted definition of halala women, as a women who profaned herself only for being a wife of a cohen, by having a relationship with non-jew, or with some one with who her marriage is prohibited, can not be considered accurate and doesn't cover all cases. 1. Being with some one who is prohibited, simply puts her into zona category. Example: Vaikra, 18.17 talks about zima, and zima is caused by zanuth (Vayikra 19:29). 2. Zanuth is caused by sexual denegradig of women, same Vayikra 19:29. " . Halala she becomes with any 1st relationship before marriage to a different person. Intention and number of parners may or may not move her from halala into zona spectrum. Just trying to decode chumash regardless of convention on the subject.
According to chumash, the only non-virgin allowed to cohen for wife is widow. This is a sufficient answer to the question. Even if she was with a jew before, any cohen has no permission to marry her. Him being with non-jewish girl/s doesn't change his cohen status.