After mulling over this question for a bit, I realized that there's a big problem with that Gemara quoted there. Shelumiel is listed back in Bamidbar 1, before the sin of the Meraglim. By the time the stories recounted in Balak happened, everyone from the previous generation had died. How, then, did Shelumiel Ben Tzurishadai survive that he could commit the sin with Kozbi?
The decree of the generation dying ended on Tu b'Av (Taanis 30b). Aharon had died fifteen days earlier, on Rosh Chodesh Av (Bamidbar 33:38). It was some time after that that Sichon and Og attacked at the end of Chukas (RH 2b makes clear that this happened after Aharon died) and it was as a result of Klal Yisrael's astonishing victory that Balak sent for Bilam (Bamidbar 22:2-4). When that plan failed, Bilam advised him with Plan B at Shittim (Rashi to Bamidbar 25:1) which resulted in the sin of Zimri and Kozbi (Bamidbar 25:6, 25:14-15). Thus, there is no room to say that the parshios are out of order, or that not everyone had died yet at this point.