I think "randomness" is even worse, because it makes it sound like these actions could be expected from anyone at anytime. Statistically, a small portion of the population is responsible for most of the violence, through repeat offenses. Also, in many situations there are clear warning signs (e.g. mentally ill with clear homicidal ideation, member of a gang). Are you really arguing that a dice roll is a good fundamental model for human behavior?
Nondeterminism (assuming humans are truly nondeterministic) doesn't really matter here, except for the fact that we don't have a way of precisely predicting people's behavior (and may never have one). If it turns out that humans are just complicated, deterministic machines that we can not feasibly predict, the reasons for which we have developed societal structures do not disappear.
> But from that same randomness we get music, science, justice.
I think it's pretty easy to distinguish between the first two and violence. I agree that the third is a bit trickier. If what you mean is that the exercise of both these and the dispositions-formerly-known-as-base-instincts are a result of allowing for a significant measure of personal freedom, I'll agree with you. But writing human behavior off as having no more structure than a random number generator ignores a lot of predictive and explanative power that we do actually have.