Ok so first I want to start by saying that I am thoroughly bored with violent games. This all came from trying to think about something that could truly replace it. But why is violence so popular in games?
So here's a couple of theories.
1. Violence is easy to program. It's far easier to program some bullets and health than it is to program complex interactions. Artificial intelligence too is much simpler when all it has to do is run around and shoot at the player. Kind of a dull point though this one, and there are always ways around technical problems.
2. Violence provides players with something to master. You see my first thought when thinking about replacing violence was something like an adventure game in which you try and find, say, a long lost sibling. You could build an entire game around this and there could be a myriad of challenges along the way involving meeting and talking to new characters mainly - but the mastery would be missing. That one core skill you practice again and again and are ultimately tested on. You could build a game without it, but something would definitely be lost.
So let's just replace it with something - for the sake of argument let's change the story. You're a tennis pro searching the land to become the ultimate player. You travel in search of new challengers. But the problem with this is that it doesn't provide the bite sized challenges that violent games do - you'd be limited to less, more meaningful encounters because a game of tennis takes a significant amount of time.
Violence is actually very well suited to a medium in which progression is so key. Bite-sized encounters hone your skill ready for the ultimate test at the end. Also from a more abstract design point of view, violence works nicely to clear the path of the blocking challenger once you've bested them, allowing you to continue on.
There is a lot that you get for free with a violent game mechanic - it fits games very well. In fact even in the real world you'd be hard pressed to find something that allows small meaningful rounds of challenge better than fighting does. I'll keep thinking though..
...perhaps a game about a wondering debater in a world full of the opinionated...
Perhaps not...
Ultimately I think the answer is to simply come up with some activity and an excuse for why everyone challenges you at it, like Pokemon. Surely though there must be a more elegant solution...