Parts of the city were indeed conquered already in Yehoshua's times or shortly thereafter. Josh. 15:63 states:
וְאֶת-הַיְבוּסִי יוֹשְׁבֵי
יְרוּשָׁלִַם, לֹא-יוכלו (יָכְלוּ)
בְנֵי-יְהוּדָה לְהוֹרִישָׁם; וַיֵּשֶׁב
הַיְבוּסִי אֶת-בְּנֵי יְהוּדָה,
בִּירוּשָׁלִַם, עַד, הַיּוֹם הַזֶּה.
"The children of Judah were unable
to dislodge the Jebusites, inhabitants
of Jerusalem. The Jebusites dwelled
among the children of Judah in
Jerusalem to this day."
Rashi and Radak there explain that the Jebusites lived in the Fortress of Zion, and that this is the specific part of the city that remained in non-Jewish hands until King David conquered it.
Malbim (to Jud. 1:8) reconstructs the events as follows: the Judahites made a first attempt to conquer the entire city in Yehoshua's times (after its king joined a confederation to fight against the Jews and was killed in the attempt, Josh. ch. 10), but failed to do so, so it became a mixed Jewish-gentile city. (Not much has changed in 3000 years!) Later on, in the period of the Judges, the non-Jewish inhabitants revolted against the Jews, so the Judahites burned the city in reprisal, but were still unable to conquer the fortress, and so that became the city's non-Jewish quarter. (Part of the city was also in the territory of the Tribe of Benjamin, and by rights they should have done their part to drive out the non-Jews too, but didn't; Jud. 1:21 criticizes them for this.)
At any rate, the main point for our purposes is that Jews were present in Jerusalem not long after their entry into Eretz Yisrael.