If kings were supposed to be from Shevet Yehuda, why was Shaul from Binyamin anointed?
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 Rambam (Hilchos Malachim 1:7-10) Discusses the annointing and appointing of Jewish kings.
There (1:8) he says:
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.
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)
But Ibn Ezra refutes Rashbam and gives his own interpretation:
כמו שאמר המשורר (תהלים עח:סז) "וימאס באהל יוסף" – זהו שילה… ואם אמרנו "עד כי יבוא שילה" כי אז תאבד הממשלה והמלכות תיפסק מזרעו, אם כן אין זה דרך המברך. ועוד כי לעולם לא יאמר "עד" בפסוק למעט כי אם להוסיף כדרך שאמר ליעקב אבינו (בראשית כ"ח:טו) "והנה אנכי עמך ושמרתיך בכל אשר תלך … כי לא אעזבך עד אשר אם עשיתי את אשר דברתי לך." (פירוש הארוך)
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:
I cannot improve on the other excellent examples, but I can provide an additional source (and one older than the others mentioned so far):
Midrash Tanchuma (Bo, Siman 5) has a slightly different version: