First, to put things in perspective a bit here, Caleb was likely a foreigner and not even an Israelite. Furthermore, Caleb is most likely not even the name of a particular person but the name of a particular tribe or clan which dwelled in the Negev. Proof of this can be found in 1Samuel 25:3 where Nabal is identified as a Calebite. Then again later in chapter 30 David talks about the "Negev of the Calebites". See alsoEven if one were to insist that those references do not necessarily prove the existence of a Calebite clan, there are other biblical texts referenced(see below) which identify Caleb with the Kenizites, and those were clearly a distinct tribe that dwelled in Canaan (Gen. 15:19). All these clues suggest that the man named Caleb in the bible was a foreigner which joined the Israelite cause to conquer the land of Canaan. Though he clearly represented the tribe of Judah in Num. 13:6, it does not necessarily imply that he came from this tribe. It is possible that he married a Judahite and through his marital relationship was associated with this tribe, or that he and his clan may have been allied with Judah, thus allowing Caleb to represent them in their expedition to Canaan (It is also possible that he came to be associated with Judah only after the conquest when Judah's lot included the Negeb where the Calebites dwelled).
Note that Caleb's lineage is not entirely clear asfrom the bible seemingly contradicts itself a few times, sometimes identifying him. Though he is mostly identified as a Kenizite (Num. 32:12; Joshua 14) a tribe which are said to have dwelled in the land of Canaan (Gen. 15); and sometimes as a, he is also said to have been the brother of Othniel son of Kenaz (Judges 3:9), the latter which probably refers to the tribe which has been identifiedsome scholars identify as a descendant of Esau in Gen. 3:11;11 (see also 1Chronicles 4:15 where the name Kenaz appears in Caleb's Genealogy as well); and then the name itself suggests that he was a Calebite. See here for more on this. It is not in my interestobjective now to offer reconciliation of these texts, but I think, judging from the few biblical texts we have, we can safely assume that Caleb was not an Israelite but a foreigner.
Note: "Caleb, son of Jephunneh (Numbers 13:6) is not to be confused with Caleb, great-grandson of Judah through Tamar (1 Chronicles 2:3-9). This other Caleb was the son of Hezron, and his wife was Azubah (I Chronicles 2:18,19)." (Wikipedia/Caleb)