A different combat system, maybe? The Dark Souls model relies heavily on player skill/dexterity as well as (or more than) pure numbers; there's plenty of room for other models to support something like that.

A first-person or third-person action model doesn't fit Pokemon very well because it doesn't position the player as the trainer, but you could do a turn-based grid like Fire Emblem, or a turn-based/real-time grid-fighter thing like MMBN, or an overhead-camera action-y thing (Diablo, most MOBAs, etc). Integrating battles into the world more (environmental things - climb trees, dig holes, hide behind rocks) could also help.