Daas Soferim on 21:38 suggests that when the cities were being allotted, there weren't suitable ones in Reuven's territory. (There are various criteria for them, listed in Makkos 10a and codified from there in Rambam, Hil. Rotzeach 8:8 - not too big or too small, in commercial areas, etc.) So the Leviim got, in effect, an IOU from Reuven to build four such cities in their territory and allocate them to the Leviim.
(Now, one of them, Betzer, had already been chosen by Moshe in Devarim 4:43. It's possible that it was already suitable, but that Yehoshua didn't want to list just that one if he couldn't list all four. It's also possible that Moshe chose Betzer even though it didn't fit all those criteria, and then instructed Reuven to upgrade it accordingly - and that this job hadn't been completed by the time the lottery was being conducted.)
By the way, Daas Soferim further notes, in his commentary on 21:3, that in the last census in the desert, the Leviim numbered only 23000 males one month and older. Even adding in the wives and newborns and girls and the oldsters who didn't die in the desert, they weren't that badly in need of all 48 cities right away.