Malchi-Tzedek is a gentile priest who worships God. I initially read this as just saying God is not exclusive (it says somewhere in Nevi'im that God also has covenants with other peoples), but today I read in Tz'enah Ur'enah that the priesthood was taken away from him and given to Avram because of the incident in torah (because he blessed Avram before praising God). This seems to suggest that, had people acted differently, Avraham might not have had the role he ended up having. How are we to understand Malchi-Tzedek?
To summarize 9 or 10 hours of Rabbi Daniel Raccah's shiurim on the subject in a single paragraph:
Malki-Tzedek is identified with Shem, Avraham's great (x7) grandfather. Noach originally aspired for his sons to be the Torah teachers in the world (like Avraham, Yitzhak and Yaakov eventually would be), but only Shem adopted the calling. That's why Shem/Malki-Tzedek is a kohen to God. Shem watched the 4 kings fight the 5 kings (all of whom were Shem's descendants) with the intention of snaring Avraham in the crossfire, and killing him. But Avraham stood up and risked his life to save Lot, and succeeded. From this, Malki-Tzedek understood that Avraham had the character traits necessary to be the primary Torah teacher in the world, and that Makli-Tzedek did not. So Malki-Tzedek went out to greet Avraham and pass the torch to him as the Torah leader of the world.
The Wikipedia article on Malchi-Tzedek bring a lot of information about Malchi-Tzedek, his interaction with Avraham, as well as the transfer of Priesthood.