Resurrection
plus I hate the idea of paying a cleric and poof the character
auto-magically is among the living once again
This is another issue when it comes to killing people. If you're willing to the kill the party, there are one of two ways of dealing with the consequences:
- Resurrection
- Make New Characters
I heavily favor option #1, because my campaigns tend to involve long running storylines and those don't work when the entire party cycles through a bunch of characters. Other people heavily favor #2, because they want combat to be meaningful and death to be a big deal.
The simplest way to make resurrection hurt without getting rid of it is to raise the difficulty of getting it. In 3.5, a Raise Dead cost at least 5000g and required you to have the body intact. For new characters, that was an impossible sum. Even for mid level characters who could afford it, that's a significant amount of wealth, and players don't want to lose tons of wealth (aka: gear, aka: power) by dying constantly. (And if the body is somewhere you can't recover it, then it gets very expensive.)
I don't know what resurrection costs are in 4e, but you can make it a bigger deal to get one via house rules if you don't like how the core game handles it. Maybe it's expensive. Maybe only one person in the country can do it (and she is obviously busy). Maybe a God will demand you undertake a quest for him after he allows your spirit to return.
How hard it is to come back is something you should figure out though, as when you do start killing people you'll want to have this sorted out already. Players should also be told what the rules around it are, if you're not using the standard ones.