Why does the verse (Bamidbar 13:16) mention that Moshe gave Hoshea bin Nun the name Yehoshua, making it seem like this was the first time Hoshea was actually called like that, but instead we see in several places in Shemos (e.g. 17:14) he is already called Yehoshua?!
The Maskil Ledavid says that Moshe prayed for Yehoshua (and changed his name) earlier, because he saw that in the future Yehoshua would need G-d's help. This is even slightly implied in the Gemara (Sotah 34B), where it says, "Yehoshua, Moshe already requested G-d's mercy for him". Already slightly implies that Moshe had done it before.
This would explain why he was already referred to as Yehoshua before the story of the spies.