We can prove that the inertial mass and the gravitational mass should be the same (equivalence principle) from the $f=mg=ma$ then $g=a$, so we have equivalence law! But why we said equivalence principle?
The original reason was that your first sentence is actually invalid: we can't really prove it (from the first principles). It's a natural assumption of physical theories, so it is a principle itself.
In Newton's theory, one could have the gravitational mass and the inertial mass as two independent and non-proportional quantities. But Galileo already knew that they were proportional or, in some sensible units, equal to one another.
This observation looked like a coincidence but it became an important observation for Albert Einstein when he was discovering general relativity. In some sense, the equivalence principle may be "proven" in the framework of general relativity. But as an assumption, it was the very reason why Einstein directed his search towards similar theories, so in this sense, it begs the question.
There are many things to be said about the validity or violation of the equivalence principle in various frameworks and about the experimental tests that it holds – and so far it does with the full precision we have. However, it may also be true that you exaggerate the difference between a "law" and a "principle". In a judicial analogy, a "principle" could be compared to a "constitutional law" – it's somewhat more important and refers to somewhat more universal issues. But otherwise it ain't such a radically different thing from a law.
The definition of a principle is "a fundamental truth or proposition that serves as the foundation for a system of belief or chain of reasoning". A statement can still be a principle even if it is known to be false.
The Oxford dictionary defines a law as a type of principle. By definition, a physical law cannot be known to be false. (There are exceptions. For example, Newton's law of universal gravitation is a law that is known to be false.)
The weak Equivalence Principle (EP) is an experimentally falsifiable hypothesis. Newton did not consider the EP to be necessary or self-evident. He performed many experiments before accepting it as a universal truth. Einstein called his version of the EP a "hypothesis of complete physical equivalence...". If the hypothesis turned out to be false, his so would his theory.
Physicists have been testing the truthiness of the equivalence principle for hundreds of years, so far it has been shown to hold at the level of 1 part in 1014. As the experimental evidence for the EP has been growing, so have the theoretical arguments against it.
Until recently there were several teams of physicists working on big budget experiments to test the EP. Unfortunately due to the global recession many of these projects were cancelled. Other equally important projects such as SETI were defunded as well. Its a shame, I was really looking forward to tossing out 400 years of gravitational theory, and talking to aliens.