If kings were supposed to be from Shevet Yehuda, why was Shaul from Binyamin anointed?
The Rambam (Hilchos Malachim 1:7-10) Discusses the anointing and appointing of Jewish kings.
There (1:8) he says:
If a prophet appoints a king from any other tribe of Israel and that king follows the path of Torah and mitzvot and fights the wars of God, he is considered as a king, and all the commandments associaed with the monarchy apply to him.
Although the kingship was primarily given to David and one of his descendents will be serving as king, there is halachic legitimacy to the rule of other kings.
The Rambam is referring to even after David was anointed and kingship was given over to King David's lineage forever, so this would surely apply before as well.
So Shmuel, as a prophet, anointed Shaul as king. Since Shaul followed G-d's commands, he was a legitimate king, even though he wasn't from the tribe of Yehuda.
Perhaps this is why, as soon as Shaul sins by not listening to G-d and keeping Agag alive, Shmuel tells him (Shmuel 1 15:23) "Since you rejected the word of the Lord, He has rejected you from being a king." and (Shmuel 1 16:14) "the spirit of the Lord departed from Saul"
Perhaps since a king who is not from the house of David is only considered a king as long as he goes in G-d's ways, as soon as Shaul sinned, he was no longer considered a king.
I cannot improve on the other excellent examples, but I can provide an additional source (and one older than the others mentioned so far):
עד שלא נבחר דוד היו כל ישראל כשרים למלכות. משנבחר דוד יצאו כל ישראל שנאמר הלא לכם לדעת כי ה' אלהי ישראל נתן את הממלכה לדוד וגו
Until David was chosen, all Israel was suitable for the monarchy. Once David was chosen, the rest of Israel was excluded - as it says, "Do you not know that the Lord God of Israel gave the kingship to David..." (Divrei Hayamim II 13:5)
- Mekhilta deRebi Ishmael, 1.4
Midrash Tanchuma (Bo, Siman 5) has a slightly different version:
עד שלא נבחר דוד, היו כל ישראל ראוין למלכות. משנבחר דוד, יצאו כל ישראל, שנאמר, לא לכם ולנו לבנות בית לאלהינו כי אנחנו יחד נבנה לה' אלהי ישראל (עזרא ד ג)
Until David was chosen, all Israel was worthy for the monarchy. Once David was chosen, the rest of Israel was excluded - as it says, "It is not for you and for us to build a House for our God, but we ourselves shall build for the Lord God of Israel" (Ezra 4:3)
Sotah 37a-b In the book Ben Yehoyadah, Rabbi Yosef Hayyim mi-Baghdad's work on the aggadic portions of the Talmud, the author points out that the reward granted to both Yehudah and Binyamin are eternal rewards - the Jewish people's monarchy will always be from the house of King David, and the place of the Temple will always remain on Har Ha-Bayit in Jerusalem. The Iyun Ya'akov argues that both rewards contain an element of monarchy, since King Sha'ul, the first king of Israel, came from Shevet Binyamin.
Nechama Leibowitz brings down the following interpretations:
לא יסור שבט מיהודה ומחקק מבין רגליו עד כי יבא שילה ולו יקהת עמים. (בראשית מט, י)
The staff shall not depart from Judah, nor the scepter from between his feet, until Shilo come, and the obedience of peoples be his. (Koren Translation) (Bereshit 49: 10)
Abarbanel points out two difficulties with the blessing as it is commonly interpreted. The blessing appears to imply that the kingship will remain in the tribe of Yehudah until David or the Mashiach will arise. This is not consistent with the historical reality in which Shaul from the tribe of Binyamin ruled prior to David, and the Hasmoneans from the tribe of Levi ruled during the second temple period. Furthermore, it is specifically at these two junctures, the assent of David and the Mashiach, that the kingship of the tribe of Yehudah was destined to be strengthened, not terminated.
According to Rashbam, Shiloh refers not to a personality, but to a location. Specifically, Shiloh, by its proximity to Shechem, refers to the place where Rechavam the son of Shlomo would come to assume the kingship. There the kingdom would be divided between the two tribes of Yehudah and Binyamin in the south, and the remaining ten tribes in the north. Thus, according to Rashbam, the blessing indicates that the kingship of the tribe of Yehudah would be secure from the time of David until Rechavam comes to Shiloh, that is during the reigns of David and Shlomo. Through this interpretation, Rashbam also dismisses the interpretation of the “heretics”1, as the blessing has no messianic reference.
But Ibn Ezra refutes Rashbam and gives his own interpretation:
Ibn Ezra refutes Rashbam’s interpretation, because it turns Ya’akov’s words from a blessing into a negative statement. He also identifies Shiloh as a location, but not Shechem. Rather, it refers to the place in which the Mishkan was housed until it was moved to Yerushalayim. Ibn Ezra associates Shiloh with the rule of the family of Yosef, Shaul2. As such, the blessing indicates that the rule of the tribe of Yehudah would begin with the transfer of the ark of the covenant from Shiloh to Yerushalayim. Ibn Ezra claims that the term “ad” (עד) in this case does not come to indicate conclusion, but rather initiation:
כמו שאמר המשורר (תהלים עח:סז) "וימאס באהל יוסף" – זהו שילה… ואם אמרנו "עד כי יבוא שילה" כי אז תאבד הממשלה והמלכות תיפסק מזרעו, אם כן אין זה דרך המברך. ועוד כי לעולם לא יאמר "עד" בפסוק למעט כי אם להוסיף כדרך שאמר ליעקב אבינו (בראשית כ"ח:טו) "והנה אנכי עמך ושמרתיך בכל אשר תלך … כי לא אעזבך עד אשר אם עשיתי את אשר דברתי לך." (פירוש הארוך)
As the Psalmist said (Psalms 78:67): “And He rejected the tabernacle of Yosef.” – this is Shilo…. And if we would say that “until Shilo comes” means that at that point he would lose the rule and the kingship would end for his descendants, this is not the nature of a blessing. Furthermore, the use of the word “ad” in a verse never comes to diminish, but to add, as our father Ya’akov said (Bereshit 28:15): “And behold I am with you, and will keep you in all places that you go…for I will not leave you until (עד) I have done all that I said to you.” (The Long Commentary)
R. Yosef Bechor Shor seems to agree with Ibn Ezra but he differs in this way:
There is a slight difference in emphasis between the interpretations of Bechor Shor and Ibn Ezra. According to Bechor Shor, the terms “shevet” and “mechokek” refer to the dominance of the tribe of Yehudah prior to their acquisition of the kingship. According to Ibn Ezra, they refer to the kingship itself.
Abarbanel offers two possible approaches:
1) "לא יסור שבט" does not mean the monarchy, but rather that Yehuda will always be inherently greater and more deserving of respect and leadership than the other tribes.
2) "לא יסור שבט" means that the tribe of Yehuda will be punished continuously throughout their exile (שבט as in "שבט אפי"), referring to the galus Yehuda that we are in currently.
As to why a king from Binyamin, Abarbanel suggests that perhaps Shevet Binyamin at the time needed some respect and elevation after its disgraceful "pilegesh b'givah" episode (besides the fact that Shaul himself clearly was worthy of the position).
The question is, “Shaul was not a descendant of Yehudah. How then could Hashem appoint a King and seemingly promise him an eternal dynasty of Kingship if he would observe the Torah, as is implied (ibid., 13:13) where Shmuel says to Shaul, ‘You have done foolishly; you have not kept the commandment of Hashem that He commanded you. For if you had, the L-rd would have established your Kingdom over Israel forever!?”
RAMBAN raises this question in Bereshit on the verse cited above, "The scepter shall not depart…" He answers that perhaps the Dynasty promised Shaul had he not sinned did not cover all of Israel, or there might have been a dynasty of second-level Kings.