The Christian "New Testament" claims Paul (Saul) was of the tribe of Benjamin.
Since Roman times have there been any people who can validly claim they were from a particular tribe?
At least at that time (Roman occupation) it was still a valid to claim.
All Cohanim and Levi'im are descended from the tribe of Levi. During the time of the temple, a Cohen would have to provide documentary evidence of their ancestry in order to serve in the temple (כהן מיוחס). Since the Babylonian exile, all such documentary evidence has been lost (with the exception of perhaps the Rappaport family). Some interesting genetic studies have also been done relating to the shared ancestry of Cohanim. Today halachically, anyone who claims to have a tradition as being a Cohen or Levi is accepted as one, for the sake of the privileges such a role entails (like getting the first or second aliyah, being able to give the priestly blessing).
Aside from Cohanim and Levi'im, there are many people who have family traditions that relate them back to Kind David (placing them in the tribe of Judah). These usually consist of direct family trees going back to a Jewish sage (rishon or achron) who lived some time in the last thousand years, and who have been related back to King David (for example, Rashi and the others).
Aside from that, no one can claim with even a small degree of certainty to which tribe they are descended from (assuming patrilineal descent). After the exile of the "10 Lost Tribes" into the Assyrian empire, there were either 3 or 4 tribes left - Levi, Judah, Binyamin and probably Shimon. Most today are descended from one of the last three (with the greatest likelihood of descent from Judah, as it had the biggest population at the time of the first exile).
In addition to what @Danny answered (Cohanim and Levites are from the tribe of Levi), several families claim to trace their lineage back to King David, meaning they are from the tribe of Judah.
Since the destruction of the Northern Kingdom of Israel during the time of the First Temple, 10 tribes were lost and we have no trace of them. The only tribes that were not lost were Judah and Benjamin (and the Levites and Cohanim who lived in their territories). Benjamin was very small numerically, compared to Judah, so pretty much every Jew alive today who is not a Cohen or Levi is probably from the tribe of Judah.
All that said, it's very difficult to "prove" any such genealogical claims; anybody could invent a family tree proving their descent from pretty much anyone they choose. We really just rely on people's good faith when they claim to be a Cohen or Levi, but there are practical halachic rulings that effectively acknowledge the difficulty in proving genealogy. For example maaser rishon (the first tithe, 10% of produce grown in Israel) should be given to a Levi - but since nobody can prove beyond doubt that they are a Levi, the obligation to give it to a Levi is unenforceable, and the owner himself may keep it.
All Cohanim and Levites are from the tribe of Levi; many people have proof of such lineage.
There is a chassidic story (I've seen it in A Treasury of Chassidic Tales by R' S.Y. Zevin; online here) in which R' Tzvi Elimelech of Dinov is told by his rebbe, the Chozeh of Lublin, that he descends from the tribe of Yissachar. Indeed, R' Tzvi Elimelech named his major work "Bnei Yissaschar" in commemoration of this.
So there's a rare case of a family with evidence of descent from a particular tribe. (Though it is possible that the Chozeh meant that R' Tzvi Elimelech's soul is associated with Yissachar, not necessarily that he was biologically descended from him.)
The Falasha, ethiopian Jews claim that they are descendants of Dan, (http://en.wikipedia.org/wiki/Beta_Israel#Tribe_of_Dan).
There is a Midrash Aggadah on Bamidbar 26:40, that says that Chusim, Dan's son, was 'black in his body'.
To add to the other answers, there is a wealth of textual evidence suggesting that at least some tribal identification remained in the timeframe between the Seleucids and the Romans and beyond.
For example, R. Yochanan bar Nafha, who lived 100 years after the destruction of the 2nd Temple, identifies himself as a descendant of the tribe of Joseph. From Talmud Bavli, Bava Metzia 84a:
The Rabbis said to Rabbi Yoḥanan: Isn’t the Master worried about being harmed by the evil eye by displaying yourself in this manner? Rabbi Yoḥanan said to them: I come from the offspring of Joseph, over whom the evil eye does not have dominion, as it is written: “Joseph is a fruitful vine, a fruitful vine by a fountain [alei ayin]” (Genesis 49:22); and Rabbi Abbahu says: Do not read the verse as saying: “By a fountain [alei ayin]”; rather, read it as: Those who rise above the evil eye [olei ayin]. Joseph’s descendants are not susceptible to the influence of the evil eye.
This suggests that at least some tribal identification was acknowledged even circa 200CE. And from the text, it appears his tribal identification was not considered an unusual or outlandish claim.
Less convincingly, but still worth noting: the Jewish Virtual Library gives additional Jewish and Christian sources attesting existence of tribal identification, often referring to them as a matter of fact. Many of these sources were written between 200BCE and 200CE, and one of these sources (Tobit) was found among the Dead Sea Scrolls community:
The belief in the continued existence of the ten tribes was regarded as an incontrovertible fact during the whole period of the Second Temple and of the Talmud.
Tobit, the hero of the apocryphal book of his name, was depicted as a member of the tribe of Naphtali;
The Testament of the 12 Patriarchs takes their existence as a fact; and in his fifth vision, IV Ezra (13:34–45) saw a "peaceable multitude… these are the ten tribes which were carried away prisoners out of their own land."
Josephus (Ant., 11:133) states as a fact "the ten tribes are beyond the Euphrates till now, and are an immense multitude and not to be estimated in numbers."
Paul (Acts 26:6) protests to Agrippa that he is accused "For the hope in the promise [of resurrection] made by God to our Fathers. It is the promise that our twelve tribes hope to attain, as they earnestly worship night and day...Why is it judged incredible by any of you that God raises the dead?,"
James addresses his epistle to "the twelve tribes which are scattered abroad" (1:1).
The only opposing voice to this otherwise universal view is found in the Mishnah. R. Eliezer expresses his view that they will eventually return and "after darkness is fallen upon the ten tribes light shall thereafter dwell upon them," but R. Akiva expresses his emphatic view that "the ten tribes shall not return again" (Sanh. 10:3). In consonance with this view, though it is agreed that Leviticus 26:38 applies to the ten tribes, where R. Meir maintains that it merely refers to their exile, Akiva states that it refers to their complete disappearance (Sifra, Be-Ḥukkotai, 8:1).
And, of course as you mention in your post, Paul the Apostle identifies himself as a Benjaminite in his letter to the Romans, dated 50-60 CE:
I say then, God has not rejected His people, has He? May it never be! For I too am an Israelite, of the seed of Abraham, of the tribe of Benjamin. God has not rejected His people whom He knew beforehand.
My family tree on my mothers side and indeed my heritage can be traced back directly to King David of Israel of the Tribe of Judah ! King David of Israel / דוד המלך is my 99th great grandfather ! Obviously I am not alone... It is reckoned that there are about 8 million of us who have a similar heritage and this makes me feel very proud of who I am !
My family can track all the way to levi himself. I've found out that allot of the biblical figures are ancestors.
Shaul said "Since the destruction of the Northern Kingdom of Israel during the time of the First Temple, 10 tribes were lost and we have no trace of them. The only tribes that were not lost were Judah and Benjamin (and the Levites and Cohanim who lived in their territories)."
Two comments: 1- Over 700 years following the Assyrian exile, we find a prophetess named Anna from the tribe of Asher in Jerusalem in the early first century mentioned in the Gospel of Luke 2:36.
2- We are told in 2 Chronicles 11 that "16 Those from every tribe of Israel who set their hearts on seeking the Lord, the God of Israel, followed the Levites to Jerusalem to offer sacrifices to the Lord, the God of their ancestors. 17 They strengthened the kingdom of Judah and supported Rehoboam."
So we see that some of the 10 northern tribes lived in the southern kingdom of Judah and would also be aware of their tribal identities.
