If it was up to me to make the games more difficult, I'd add a simple level cap. For instance, until you have beaten the first Gym Leader, no Pokemon may grow beyond level 10. You're free to train as many 'mons as you like up to level 10, but nobody will receive any exp. once level 10 is reached. Good bye grinding. Once the Gym Leader is beaten, the bar is raised to, say, 20. Do note that the Gym Leader's top levelled Pokemon won't neecsarily be below the bar. The first Gym Leader could have his 'mons as high as level 13-15.
For extra fun, do as proposed above and make the Gyms be a gauntlet challenge. Once a Gym is entered, its doors are closed and you may not use any medicine items (not sure about holding items). The doors will open upon the defeat of the Gym Leader. If you lose, the Gym Trainers will reset and you have to fight them all again upon your next visit to the Gym. Same goes for the Elite Four, which admittedly would be a very small change from the current procedure.
More fun? Limit Pokemon centres. Have them only open up after the local story event is cleared (such as Slowpoke Well in Azalea Town, for instance, or SS Anne in Vermilion City). Problem solvable by flying/walking to the previous town, you say? Then limit backtracking in the same fashion. Once you enter a new area, you can't go back (leave the Well/disembark the ship) until you've cleared the bit of story and opened the Pokecenter. In other words, it'd be vital to stock up on supplies before departing a "cleared" town. If you're defeated, you're thrown back to the last town, and have to try again. And because of the level cap, grinding would only help you so much. If you keep losing, you can catch new Pokemon and train them to be used in the troubling area. Backtracking to find useful new team members would now almost be a requirement rather than a pointless chore.
This would make certain "broken" items such as the Lucky Egg or the Exp. Share far more bearable. Instead of boosting your team members way beyond any resistance, they would be useful tools for making new team members catch up to their teammates a lot faster. Because of the level cap, there's a limit to how much the "oldies" can outrun new recruits anyway.
This also means players could pull a Pokemon Origins and alter their team drastically as the game passes, to the point of tailoring it against the problems they encounter. If the game designer manages to give opponents the right battle strategy, you'd actuallly need to consider teambuildng in-game in order to pass through the most difficult areas.
Sprinkle this with money issues as you see fit. Enabling players to fill a bag with Full Restores would make it too easy for them, on the other hand it's unwise to punish repeat losers too badly by denying them access to sorely needed healing items when they go bankrupt. Perhaps a credit card solution could be an option? Let bankrupt players shop for, say, 10 000 pokedollars before they can enter Victory Road. The money earned in battles will not go to the player's purse, but paying off the debt. If they still are indebted heavily after losing and blacking out, they can try to enter the area again without buying anything first. Even without healing items, they can surely beat the first few trainers and pay off a bit of their debt before being knocked out, and even after paying the loser's fee, they would be better off than before. If the first trainer in the area is the problem, repeatedly defeating the player before money can be earned, there's always Meowth and Pay Day. Hi again, grinding.