I will try to offer a heuristic argument for the assignemnt of energy as the zero component of the four-momentum. (And I'll use units such that $c=1$, so that velocities are in fractions of the speed of light.)
First one should realise that there are really two aspects here. "Kinematic" variables, such as velocity, describe, say, the motion of particles -- all we need for these to make sense are some definitions of what we mean by position, time etc. Hence, in the transition from Galilean space and time to Minkowksi spacetime, these quantities change due to the differnet underlying structure, in particular Lortentz invariance.
On the other hand, "dynamic" quatities such as momentum, energy or mass are really only meaningful in the context of dynamical evolution laws, i.e. some equations that tell us how particles evolve in time, interact with each other etc. In particular, momentum is an important quantity in Newtonian mechanics because it is conserved in time due to the equations of motion. So we would need to specify some dynamical equation of motion, or equivalently an action, and see what are the conserved quatitied and how they compare with classical mechanics.
I will only look at the first part and assume that there is some dynamics that reasonably reduces to classical mechanics without specifying the details. Note that this Newtonian limit will only be reasonable for massive particles -- the state of massless particles is quite dubious here.
So assume a massive particle moves along the $x$ direction. In the coordinates of an intertial observer, its path and four-velocity would be
$$ x^\mu=\left(t,v t, 0,0\right)\,,\quad u^\mu=\left(1,v,0,0\right)\,.$$
The square of the velocity, which is Lorentz invariant, is $u^2=1-v^2$. Now consider a second observer which moves along with the particle. The four-velocity accordeng to her, $w$, will be related to the first one by a Lorentz transformation, which in this case involves four parameters,
$$ w^\mu=\left(a(v) +b(v)\cdot v,a(v) \cdot v + b(v),0,0\right)\,.$$
(The fact that a Lorentz boost takes this form is left as an exercise at this point.) Since clearly $w_x=0$, we have $b=-a \cdot v$, so $w^\mu=\left(a(v)\left(1-v^2\right),0,0,0\right)$. Since Lorentz invariance demands $w^2=1-v^2$, we have $a=\gamma=1/\sqrt{1-v^2\,}$ and
$$w^\mu=\left(\sqrt{1-v^2\,},0,0,0\right)\,.$$
Now there's really no point in having an arbitrary velocity $v$ in the four-velocity of a massive particle in its rest frame -- after all, we could have started the argument with the rest frame instead. Furthermore, these are coordinate expressions, not velocities with respect to eigentime. Thus, we'll divide the velocities by $\gamma$, and the final, heuristically reasonable, four-vector that generalises the velocity is
$$ u^\mu=\left(\frac{1}{\sqrt{1-v^2\,}},\frac{\vec{v}}{\sqrt{1-v^2\,}}\right)\,.$$
In the rest frame, this reduces to $(1,0,0,0)$, which makes sense - a stationary particle moves into the future at unit speed. However, the basic fact that, in the change from one reference frame to a boosted one, the $\gamma$ factor appears is simply a consequence of Lorentz invariance. Also note that $u^0\geq 0$ -- there is a minimum "$t$-speed".
Now the obvious guess for the four-momentum of a massive particle becomes $P^\mu=m u^\mu$, and that's what you have in the original question: It is a proper four-vector, and in the Newtonian limit its spatial part reduces to $m\vec v$. But what is $P^0$? Again, we can look at the low-speed limit $v\ll1$ -- then we have
$$\frac{m}{\sqrt{1-v^2\,}}\simeq m\left(1+ \frac{v^2}{2}\right)=m + \frac{p^2}{2m}\,,$$
an expression you can recognise as "rest energy" plus Newtonian kinetic energy. If you now additionally impose that, whatever dynamics govern mechanics in special relativity, Newtonian mechnics is recovered in this limit, you end up with the relativistic expression $P^\mu=\left(E,\vec{p}\right)$, and $P^\mu P_\mu=m^2$.
This argument doesn't work directly for massless particles. But we still get some information out:
A particle moving with $v=1$ (i.e. speed of light) in one frame of reference does so in all of them (otherwise we would have $v^\mu=(0,0,0,0)$ in some frames). So there is no preferred rest frame, and the four velocity is always of the form $(\left|\vec u\right|,\vec u)$ for some three-velocity $u$.
This already means that speed-of-light particles are not at all similar to usual massive particles: The "$t$-speed" $v^0$ can be made as small as we wish (but not zero). On the other hand, there is no obvious notion of energy or momentum for massless particles in Newtonian mechanics.
The plausible answer is then to assign a four-momentum $P^\mu=\left(E,\vec p\right)$ to massless particles, with $E^2={\vec p}^2$: It is a proper Lorentz four-vector and $P^\mu$ is proportional to $u^\mu$, and the energy-momentum relation fits with the one for massive particles. Of course, to argue that this is the energy of a massless particle, you have to fix the dynamics, i.e. an equation of motion or an action.
In any case, the pairing of energy and three-momentum into a four-vector is the plausible one to get a proper Lorentz four-vector.
