The Torah says Yehoshua was "bin Nun", the son of a Catholic nun. Does this mean that Yehoshua had to convert to be a part of the Jewish people (which might explain his name change from Hoshea to Yehoshua)? Perhaps his mother was indeed a Jew but she converted out of the faith? Whatever the possibility, his mother was obviously a bad nun as nuns are supposed to be celibate.
This question is based on a misunderstanding. The Torah was not written in English, so his mother was not a nun. Rather, נון is the Aramaic word for fish.
See Bechorot 8a, where the gemara writes: הדולפנין פרין ורבין כבני אדם where Rashi emends the text and writes: ה"ג הדולפנין פרים ורבים מבני אדם - שאם בא אדם עליהם מתעברות הימנו:
that "dolphins" interbreed with humans, meaning that if a human has intercoure with them, they become pregnant from it.
Thus, Yehoshua was a merman.
Indeed, one might then have questions about his status, since a fish is not Jewish and we follow matrilineal descent. However, Yehoshua bin Nun was present at Mattan Torah (see Shemot 32:17), and before Matan Torah, patrilineal descent was the rule. See here, for example.
You've totally misread the text! In the Bavli Talmud, written in Aramaic, the good man is referred to as "Yehoshua Bar Nun" i.e. "Bar None", as in "the best ever".
As for the name change, there is a well-known midrash explaining that Moshe was constantly calling him over by saying "Yo, Hoshea" and it just sort of stuck.
Yehoshua 'bin נ' means that the number Nun, or 50, is supposed to be written in BINary. 'bin' is the designation that the number that follows is a binary number. Yehoshua used to wear a jersey that said 'Yehoshua 110010' as we today would write 'Yehoshua 50'. The 1s and 0s actually indicated victory (1) and loss (0). Moshe Rabbeinu saw prophetically that Yehoshua would be battling 6 canaanite nations. One nation would run away, leaving 6 or the original 7 for Yehoshua to battle, hence a 6-digit binary string. Each of the nations was designated a specific location in his binary string. Moshe Rabbeinu also foresaw that Yehoshua would not complete the settling of the Jews in the land. Moshe indicated this to Yehoshua by having some of the 1s where he accomplished the settling, and the 0s represent unsettled tribes left for after his death.
There were 31 kings in the land of Canaan when Yehoshua came in. He designated a bit position in a double word byte (32 bits altogether) to track elimination of each one, leaving himself in the final primary bit position.
Yehoshua was into people wearing Jerseys. Each tribe would go out to battle with a different colored jersey, with the color that matched that tribes Degel (flag). If he encountered someone without a Jersey, he would typically approach him, bow, and ask 'Are you for us or against us?'.
The binary notation is seen in other areas of the book of Joshua as well. He encircled the city of Jericho 7 times because 7 in binary is designated as 111, which signifies victory all around.