I don't see a problem with a "free roam" game. Why? Because they'll design the region with that in mind. Yeah, this doesn't work for previous Pokemon games settings because the region was designed to be experienced by a certain path through the region. But a region meant to be "free roam" would be designed that all the major Cities/Towns are accessible.
"Wouldn't that completely ruin the sense of adventure if you went to all the Cities and Towns before getting to the game's story?"
No, because though they'll have the Cities/Towns all accessible they can still block off routes/forests/caves/etc. that would unlock as you progress. While for general locations this could be simply getting the right Badge/Crystal/Symbol/McGuffin to use the HM/Poke Ride/or show to the guard. These locked off locations could either be side locations or be new shortcuts, but they're main purpose is to provide new areas to catch Pokemon and maybe have story bits, be them part of the main story or side stories. In addition, you can layer the unlockable locations so that as you get access to more HM/Poke Rides/explorer items you can explore deeper into areas where more mysteries are to be found and, more importantly, higher leveled trainers and wild Pokemon. And they can make the progression area specific. Like (using HMs in this example) there could be a forest where you'd first need Cut, but then to go deeper you'd need Rock Smash, than Strength, than Surf, than Rock Climb. But then somewhere else there's an island you'd first need Surf, to go deeper you'd need Rock Climb, than Strength, than Cut, and Strength. And so on and so forth, each area's terrain being made so you'd need a different order of HMs/Poke Rides/explorer items to get through.
Also it goes without saying if they do this they'd need to make sure what you need to do to explore deeper into an area doesn't hamper the player's team. Not an issue with Poke Rides or explorer items (aka HM items which players been asking GF to make), though is something to keep in mind with HMs. The easiest solution there (aside letting the player carry around some extra Pokemon), would be having services like PokeRides you can call on or getting the explorer item that does the same function.
"But what about the story progression?"
For the story that could be determined by the amount of Badge/Crystal/Symbol/McGuffin you got (or just hidden flags that check off as you do them). For the Pokemon League this would mean making multiple team sets. Though honestly all that means is that each Gym Leader would need eight different teams, the only group with multiple members is the Elite Four who since Gen V you could battle in any order yet they don't change their team if you beat a previous Elite Four (that said they should probably increase their levels each time you beat the Pokemon League).
As for the villain team story or whatever they're having in its place, that could just be left as is. Easiest thing to do there would just have that gen's assisting tool (PokeGear, PokeNav, Poketch, C-Gear, Holo Caster) have a radio/TV function and when it's time for story progression the function has an alarm that goes off and you hear a report of something happening at a certain town or location, which is your cue to go there (at this point any progression is put on halt so you can't just go get another Badge or do side quests). As you progress maybe you'll get to know certain characters (the Pokemon League, International Police, a spy, maybe accidentally befriending a grunt or signing up for the villain team's schedule planner) who will give you a call or message that something is going on someplace. Now you don't have to change the levels of the Grunts or Admins. Now maybe they can include moments where you can pick to battle a certain admin over another and later battle the admins you skipped over, thus they'll have different levels/Pokemon than, but that would just be if they wanted to do something neat like that.
"But wouldn't there be a risk of your Pokemon's levels getting too high?"
This is probably the major problem and would require the most extreme change: level caps. You know how high level traded Pokemon wouldn't listen to you if you didn't have the right amount of Badges? Same idea, except here it means the Pokemon can't level up until you get the next Badge. It'll still earn experience, but until you get the next Badge that experience won't be added (sort of like how in the Colosseum games Shadow Pokemon didn't get to level up from their experience points until they've been purified). Also they could have the trainers you battled refresh and/or add new trainers to battle with higher level Pokemon (not to mention the trainers you'll now have access to in the unlocked areas you can now get to). This might also encourage players to maybe train up more than just their core group of six Pokemon if they go on a training binge after each Badge and battling as many trainers and higher level wild Pokemon as they can. They can try out a new Pokemon they caught or maybe train up an ace-in-a-hole for the next Gym Leader they plan on battling. This could also be used to create interesting boss battles as you could have the Gym Leaders, Elite Four, Champion, Rivals, and villain team Admins & Boss use Pokemon who level is above the cap thus you'd have to play smarter to beat them (though maybe have a fail safe if the player loses to them, like have difficulty levels they can toggle in the Options or, if they continue playing after losing, have the boss's Pokemon level drop to the cap max).