I try to solve problems from a systems perspective. For example the common automobile stop and warrantless search allows officers to more easily abuse power and escalate situations quickly as cops no longer required a warrant from a judge. This was by design by the Supreme Court who ruled in 1925 to allow this exception in times of prohibition when an individual ran away from police with alcohol and they didn't have time to go get a warrant. Stop and frisk was an extension of this case law.
If people no longer trust that executive arm of government, then hold those in power responsible for it. Start at the top and replace those politicians. An elected politician can only remain in office if they continue to receive support by voters.
Just voting differently is naturally not the only way a government can be held responsible. Political assigned jobs is a job description based on trust, and there should be mechanism to remove individuals who do not fulfill that trust. Governments should also be liable to their citizens, so when injustice occurs people should have the option to demand compensation from the government. This in turn put pressure on politicians to avoid injustice caused by the police.
A police force that protects citizens rights should be viewed as an asset to local government, and the opposite should be a harsh liability that local governments can feel.