I was surprised by the popularity of my previous question about Kain and Abel, but msh210 mentioned that that wasn't so special and indeed, we find another example in the open text of the Torah that a non-firstborn not only brought sacrifices but served as a priest (Ber 14:18) - Malchitzedek, aka Shem Ben Noach:
וּמַלְכִּי־צֶדֶק מֶלֶךְ שָׁלֵם הוֹצִיא לֶחֶם וָיָיִן וְהוּא כֹהֵן לְאֵל עֶלְיוֹן׃
And King Melchizedek of Salem brought out bread and wine; he was a priest of God Most High.
The Jer. Targum says: "וּמַלְכִּי צֶדֶק מַלְכָּא דִירוּשְׁלֶם הוּא שֵׁם רַבָּא הֲוָה כָּהִין עִילָאָה:" - "Melchizedek, the King of Jerusalem, he's Shem, was High Priest".
As my previous question explained, before the tribe of Levi was designated for the High Service, the firstborns were assigned that role. However, once again, Shem wasn't Noach's firstborn, as per Rashi in Ber. 10:21, but Yefet was. So even if we assume that Abel was able to bring sacrifices because they were personal, Malchitzedek actually serves as a priest (unclearly what exactly though).
I admit that I don't fully understand the idea of serving G-d before the Matan Torah and Mishkan, etc, but I think the question is legitimate.
How those two facts can be reconciled?