Can special relativity be deduced from $E=mc^2$? So instead of assuming that the velocity $c$ is a maximal velocity, proving that while assuming $E=mc^2$.
 A: Usually, the cornerstone of Special Relativity is the constancy of the speed-of-light: form this fact alone, much of Special Relativity can be "deduced". (For a very interesting article about this point, see Relativity without light, by David Mermin.)
Further, this formula for energy is just an approximation of the fully relativistic expression, cf Mass-Energy Equivalence.
A: These two concepts are not related at all, so it's not possible to deduce anything either way.
Special relativity in its bare form talks only about space-time, i.e. geometry. You don't have any energy or mass there without first somehow postulating what it is.
For the reverse direction: you can't really deduce anything about SR from $E = mc^2$ because $E$ and $m$ could be anything (in particular you don't know whether $E$ is a component of a four-momentum $p$ or something completely different). And even if you knew what $E$ and $m$ was that would still give you no clue about what $c$ is (and that it should be constant in every inertial frame).
A: Here is a quick result that might interest you:
Let's begin from the equation of relativistic energy in terms of the rest mass, $m_0$, $E=\gamma m_oc^2$, then by inserting $\gamma = \sqrt{\frac{1}{1-\frac{v^2}{c^2}}}$, we find:
$\hspace{6cm}E^2-E^2\frac{v^2}{c^2}=(m_0)^2c^4$
Hence:
$\hspace{6cm}E^2=(E_0)^2+p^2c^2$
which is the equation that relates relativistic energy and momentum.  So maybe the best we can say is if you start from the equations $E^2=(E_0)^2+p^2c^2$, and $E=\gamma m_oc^2$, we can derive the Lorentz contraction. 
