On the topic of the ability to face gym leaders in varying orders in the older games, the first question that comes to mind is: who cares?
well getting rid of the forced linearity of the gyms allows the player to feel that he has a choice on how to play the game. using passage restriction with HM is a cheap way of enforcing how the gameplay unfolds. they could easily do somethin like:
city 3
||
||
||
||
||
city 2============roadblock===city 5=
||
||
||
||
||
city 4
where the sequence of doing cities 2, 3 and 4 depends on the player, with the roadblock preventing the player to continue without the three badges. it would even be neat if the sequence on which you defeat the gyms affect the game somehow.. the level and pokemon of the gym leadears might vary based on this.. for example, there are six different ways on which the gyms can be taken..
city2 (venonat, lvl 10, Kricketune lv10, scyther lv12)
city3 (koffing, lvl 16, muk lv16, nidorino lv18)
city4 (carnivine, lvl 20, lombre lv22, tangrowth lv24)
city2 (venonat, lvl 10, Kricketune lv10, scyther lv12)
city4 (lombre, lvl 16, skiploom lv16, tangela lv18)
city3 (swalot, lvl 20, weezing lv22, nidoking lv24)
city3 (grimer, lvl 10, arbok lv10, nidorino lv12)
city2 (surskit, lvl 16, venomoth lv16, scyther lv18)
city4 (carnivine, lvl 20, lombre lv22, tangrowth lv24)
city3 (grimer, lvl 10, arbok lv10, nidorino lv12)
city4 (lombre, lvl 16, skiploom lv16, tangela lv18)
city2 (shuckle, lvl 20, masquerain lv22, scizor lv24)
city4 (hoppip, lvl 10, roselia lv10, tangela lv12)
city2 (surskit, lvl 16, venomoth lv16, scyther lv18)
city3 (swalot, lvl 20, weezing lv22, nidoking lv24)
city4 (hoppip, lvl 10, roselia lv10, tangela lv12)
city3 (koffing, lvl 16, muk lv16, nidorino lv18)
city2 (shuckle, lvl 20, masquerain lv22, scizor lv24)
(just random pokemon and levels, so yeah they might be imbalanced or something).. i don't think this is too hard to pull off, and while they are at it, they can also increase the general level of the wild pokemon everytime a badge is earned.. as long as the subquests, if any, in each route are not too interrelated, then i dont think there's much problem with letting the player roam around on his own accord..