I must agree in almost everything but not all:
Gym Order: Why make it an order? What they need to do here, is instead of making the region setup so you HAVE to do Gyms in a certain order, why not make it so you can get to every Gym of the game right from the start? But how would this work, some might ask?
I like the idea of going to any gym you would want to go, but you are saying go from A gym to Z gym, just to battle Z gym first sounds weird, why would someone go to the last gym and not beat the first one? perhaps more than changing the orders is to make a good map that allows the player to go from gym A to gym G without realizing he is not going in the "right" order, the deal here is trick the player to not know what order there is, and whatever path he takes he is doing a right thing.
the other ones I really agree on that, here are some other solutions:
Random start:
Start in a random city, this will probably benefit more the beat any gym in whatever order,and make it so professor X is in town searching for new trainers, so he gives you a pokemon, this also heavily depends on the map, if the HM still apply you must make the map in a way that the player can beat or can reach all areas without getting stuck.
No lvl up:
This might sound weird but in the anime if pikachu was in a game he would be lvl 100 and he still fails to win sometimes, now in game how about making each pokemon not level up? so even if you are in route 1 with a last evolution pokemon you can still die to a pidgey, or if you have a magikarp caught at the start of the game you can win any other pokemon, this might sound crazy, but perhaps making the player win xp and suddenly learning a new move, so now you might be wondering what would be the difference between a pidgey in route 1 and a pidgey in route 35? well it's easy, the route 35 pidgey will have different or more moves than a route 1 pidgey, this way it will not only be easier to make people go in whatever direction they want but if done right each time you fight it might be a fight you will actually lose.
And lastly one that might not work:
Perhaps limiting the pokeballs or the pokemons you can catch will make player appreciate more their pokemon or think twice before knowing what to catch, and once you beat the league this rules are nullified, this can be done by saying Bill's PC is broken and can only handle X quantity of pokemons.
And lastly any
Nuzlocke's rule applied to the actual gameThis takes the game to a whole new level making you appreciate the game even more and making a really crazy challenge. The first pokemon of each area is the only pokemon you can catch in that area or if your pokemon dies in a battle it actually DIES not faint