I agree with Petr that the answer to this really depends on what you're willing to assume.
Suppose you want these things: (1) A four-vector exists that is a generalization of the momentum three-vector from Newtonian mechanics. (2) The relationship between the relativistic and Newtonian versions satisfies the correspondence principle. (3) The quantity is additive (because we hope to have a conservation law). Then I think it's quite difficult to come up with any other definition for the momentum four-vector than the standard one, and then the E^2=p^2+m^2 identity follows immediately. But this isn't anything like a proof of uniqueness or self-consistency.
Petr's derivation is likewise very natural, but it depends on the assumption of a certain form for the action, and there's no guarantee that the results it outputs obey the correspondence principle or result in a conservation law. Those properties have to be checked mathematically and experimentally.
There's a variety of very persuasive physical arguments that once you've accepted SR's description of spacetime, you have to believe in mass-energy equivalence. A good example is Einstein's 1905 paper "Does the inertia of a body depend on its energy content?," where he does a thought-experiment involving an object emitting rays of light in opposite directions. He only says there that "The fact that the energy withdrawn from the body becomes energy of radiation evidently makes no difference[...]," without giving any real justification, but it's not hard to come up with arguments to that effect (see, e.g., http://www.lightandmatter.com/html_books/genrel/ch04/ch04.html#Section4.2 , at "the same must be true for other forms of energy"). No amount of mathematical manipulation can substitute for this kind of physical reasoning, or for empirical verification.