The Gym Leader's Pokemon would obviously be influenced by what is available in the Johto-dex. With that in mind, and with minimal guess-work as to which pokemon from 3rd and 4th generations might make it in, here's my guess for the Gym Leader and E4 teams. And yes, I also agree that the levels do need to be increased. I also believe there should be at least one or two more towns/grinding locations available between the events of the sixth gym and the E4. That's just me though.
-Falkner-
TM: Aerial Ace or Roost
-Level 8 Skarmory
-Level 10 Natu
-Level 14 Hoothoot
Note: If this is to work, considering the short distance between the beginning of the game and the first gym, wild encounters should be increased by 2-3 levels one or two routes in order to provide enough experience. Remember, Geodude and Phanpy are available for counters before facing Falkner as of this point, at least in Crystal. Skarmory might require Mareep becoming available earlier, or Cyndaquil to be your chosen starter without massive grinding or attrition. Also, I gave in on the idea that most of the Johto leaders should have Johto pokemon. Fortunately, this works for Falkner.
-Bugsy-
TM: U-turn
-Level 11 Spinarak
-Level 13 Yanma
-Level 15 Heracross
-Level 18 Scyther
Note: Going off the original games, there's not quite enough variation in pokemon between the first two gyms to allow for a huge advantage here (Geodude/Graveler, Cyndaquil/Quilava, and a Spearow/Pidgeotto). However, I'd say it's still definitely possible with enough grinding and some trades.
-Whitney-
TM: Attract or Return
-Level 18 Teddiursa
-Level 20 Eevee
-Level 22 Clefable
-Level 24 Miltank
Note: Easily manageable, if you scout ahead to get a Machop (which was available via trade at about the time you get to Goldenrod City anyway). Yes, I evolved the Clefairy.
-Morty-
TM: Shadow Ball (not much choice, here)
-Level 23 Haunter
-Level 25 Misdreavous
-Level 28 Gengar
-Level 30 Mismagius
Note: This should be fairly challenging, though not overwhelming, I'd think. Psychics will only get you so far, so Dark-attacks will be required to seal the deal at this point. If newer pokemon are available, I would replace Haunter with Shuppet or Duskull.
-Chuck-
TM: Bulk Up and/or Brick Break
-Level 30 Machamp (No Guard)
-Level 32 Heracross
-Level 33 Poliwrath
-Level 35 Hitmontop
Note: You should have access to enough grass and electric-type attacks by now to be able to take on Poliwrath, not to mention Flying techniques. Especially if Aerial Ace was given by Falkner or is available sometime before now.
-Jasmine-
TM: Iron Tail or Gyro Ball
-Level 34 Scizor
-Level 36 Magneton
-Level 38 Forretress
-Level 41 Steelix
Note: With fire-type availability, this should be a cinch. If Lucario was available, I'd replace Forretress with one. Even if Magnezone is somehow available, I would not replace the Magneton in this line-up with one.
-Pryce-
TM: Avalanche
-Level 36 Dewgong
-Level 39 Piloswine
-Level 42 Weavile
-Level 44 Mamoswine
Note: Again, with Fire, Steel, and Fighting types this should be simple.
-Clair-
TM: Dragon Pulse
-Level 42 Gyarados
-Level 44 Seadra
-Level 46 Dragonair
-Level 50 Kingdra
Note: If I was to include another Dragon-type from newer games, I'd replace Seadra with Flygon and throw in a Level 45 Altaria to start with. I would suggest Milotic as well, but honestly, Clair never struck me as a Coordinator-type.
In my opinion, and considering the sheer lack of original 2nd Gen pokemon (and how a fair number of them are not very good pokemon, namely the Sentrets and Stantler kinda pokemon), I think keeping a fair number of Kanto pokemon in the gym leader's teams is pretty much required. I didn't add any 'new' pokemon other than generational evolutions (such as Mamoswine, Weavile, Mismagius, etc) into consideration. I did jump their levels up quite a bit, however, compared to what they used to be. Considering that most players at least understand type advantages these days, they'd have to exploit them in order to take out the pokemon at these levels (without level grinding and/or breeding by around the third gym).
I do realize that there's a big issue with the number of available trainers to battle and wild pokemon to grind levels on, so there are a few options that present themselves: grinding in the wild and waiting for Match Calls as well.
Honestly, I think that this could be done. There's an average of 4-6 levels between the max levels of each gym leader, and the levels aren't that much higher except at the beginning. As mentioned above, increasing the levels of pokemon found on Route 46 by a few levels should do the trick.
For the E4 and Kanto teams... well, enough has been said on those, I think. And, it's late.
That's my 2-cents. Sorry, I don't have any change for ya right now.