Strong government is the answer. Mexico's government is weak. The state does not have a monopoly on violence.
It's not that weak. The organized crime is strong, because Americans love to buy Mexican drugs, which is a whole other debate.
Punish rock possession with summary execution and you will stop people from being stoned to death.
Really, i can rest my case, if you are serious about that.
America used to be far more violent than it is today. If there has been any cultural change, it has been an improvement.
I don't think it is a cultural change, however. The United States has become a progressively stronger state. The police force has become progressively more effective at enforcing lawful behavior among its citizens.
For 2/3 of the time in the chart you cited, America was a frontier nation, trying to subjugate or kill off the indigenous population, and many people living in areas without police. Cowboys or the army shooting it out on the frontier is not the same as shooting defenseless people in a building...
We had that kind of strong state in the Soviet Union, where gun violence was rare yet still existed. Everyone, including the criminals, was pretty safe from gun violence. I understand why state agents or members of a country's upper class would advocate for such a state, but in practical terms, it's only desirable in theory.
Most of the Russians don't want that kind of strong state back, even though it was "safer", because that kind of a state comes with a lot of other restrictions, which would mainly benefit state agents and the elite.
If you want to do even better then today (near the US historical best in terms of violent crime rates), then you will have to repeal the 2nd Amendment, restrict gun ownership to state agencies, and aggressively enforce this law.
Or you could pull American armies from their numerous bases in other countries, and have them become security guards at American school, or border guards. If what you said about violence reduction due to effective police is true, America needs more such police in "gun free" zones more than it needs impractical private gun ownership prohibition.
The homicide rate in Singapore (perhaps the strictest prohibition of firearms in the world coupled with strong, incorruptible enforcement; any private discharge of a firearm = capital punishment) is one-fourteenth of that in the United States.
Speaking of
Singapore, its firearm laws seem to be more like some of the more restrictive American states, such as CT - automatic weapons, multiple weapon possession, unlimited amounts of ammunition, carrying in public concealed or openly, and so on seem to be allowed with a license and training.