Perhaps the best solution is to have more democracy or community input into policing. It seems like it's happening now in the US (it would be quite different in other countries, where the police is national and considered civil servants; in France you can't elect sheriffs, and police is beyond the responsibility of mayors).
In the end, some communities will vote for a police that's tough, and other communities will vote for a police that's less tough. There will still be issues when criminals used to non-tough cops cross into an area with tough cops, but that's life.