How difficult do you want to make it for the PCs to be actual murder hobos? I think any setting with large rural estates will work. In such settings, the forces of law and order are not powerful enough to stop the PCs (unless really riled) while there's enough victims.
It's actually hard to find a setting like that, though. I was thinking about Eberron, but every city seems to have a competent police force, or failing that, the mayor can hire Power Group X to hunt down the PCs.
Or were you talking about a campaign where PCs are rootless, not necessarily horrible people, but ones who avoid civilization, duty, etc.