Reduce the amount of AMMO found in the world by A LOT. This way guns are OK but it is the ammo that should be conserved and used when it really is needed.
This also adds a new layer to the game because when you see someone you know ammo is rare so you have to think, does he have 1 in chamber? Does he have any in that mag/clip?
It will also stop the random killings, more or less...because ammo will be so rare it could even become tradable.