@Cam, if you are going to make a non-linear game, then it has to stay true to the idea of all the other games. But you shouldn't feel confined to making it like that just because people at the beginning of this topic mentioned that. Creative freedom applies..
My idea is as follows;
When you select new game, you are asked which set of Pokemon games is your favorite. Red+Blue, Gold+Silver, Ruby+Sapphire, or Diamond+Pearl. If you choose Red+Blue as your favorite, your starter Pokemon options will be Bulbasaur, Squirtle, or Charmander. Whereas if you choose Gold+Silver as your favorite, your starter options will be Chikorita, Totodile, or Cyndaquil (you get the idea).
The game begins in a giant airplane where you live with some new Professor, the player can be his grandson or granddaughter or something. There he tells you that you need to go out and see the world, blah blah, there's more to it than the walls of this airplane. He suggests training to become a Pokemon master and gives you your choice of a starter Pokemon.
From there you can choose which region of the world you want to land in and start your journey. Whatever area you choose to start in then has the easiest set of gyms. When you finish all the gyms in that region you'll get picked up by the Professor in the airplane and he'll ask you how everything's going so far. Then you can choose the next region you want to journey to, which will then have increasingly more difficult gyms, etc. This way it's actually kind of linear still, but will feel non-linear in that you can choose where you want to go. As far as HM moves, I'm sure you can spread out where you find them over all the regions. Then once you beat all the gyms, whatever you choose to be your last area will have the hardest set of gyms, you can go wherever you like in your plane and go back to areas with new HM moves to access older areas you couldn't reach before.
Then have some sort of ultimate Elite Four that is on some obscure new small island the plane can go to but you need all the gym badges from every area to go to. It'd be like a Global Elite Four instead of just an Elite Four for each region.