How Okami did it

In Okami, the player gain experience and can then use that experience to improve the character's stats. There are two ways to gain experience: Through exploring the world, and through progressing the story. Gaining experience from progressing the story is simple, when the player defeats a boss or completes a mission (including side missions), he or she is rewarded with some experience. Exploring the world allows the player to find places where experience can be gained. The player can gain experience by feeding animals, reviving withered clovers (the game is made by Clover Studio), and by making cherry trees blossom. Each group of animals can only be fed once, each clover can only be revived once, and each cherry tree only need to start flowering once.

This has the effect that there is only a fixed amount of experience points to be gained in the game, and it is also relatively easy to know roughly how much experience the player will have at any point in the game, since the player must have completed certain experience rewarding tasks to get to a that point, and also there are only so much exploring and side tasks available before that point.

There is a certain entertainment value in exploring, finding something new, or hidden is fun, it's rewarding. Particularly in combination with actual, game relevant rewards. Exploring does not have the same, repetitive nature as grinding, since there is little need revisiting the a place when exploring. The drawback, of course, is that you have to produce interesting areas to explore (see Shadow of the Colossus for what is probably the best example of this, I have never ever in a game so thoroughly enjoyed just exploring the world, wherever you go, you find a beautiful, intriguing new place).

The whole point of this example is not that every game should replace experience gained by killing monsters by experience gained from exploring. It is rather to point out that there are alternative ways to reward experience. As gaining experience is normally a very important part of the game, players will naturally engage in a behavior that rewards them with the most experience. Realizing this, and you can use this to your advantage, guiding the way the player plays your game, to maximize the player's entertainment.