Why are Hamiltonian Mechanics well-defined? I have encountered a problem while re-reading the formalism of Hamiltonian mechanics, and it lies in a very simple remark. 
Indeed, if I am not mistaken, when we want to do mechanics using the Hamiltonian instead of the Lagrangian, we perform a Legendre tranformation on the Lagrangian to get the Hamiltonian. This, in the case of a 1 dimensional problem, is written as follows:
$$ H(p,q) = p\dot{q}-L(q,\dot{q}).$$
Notice that this transformation is such that $H=H(p,q)$, where $p = \frac{\partial L}{\partial \dot{q}}$. By variation of $H$, we can indeed verify it as function of $p$ and $q$, so that they are now considered the new independent variables of the problem.
So far so good. However, there is a problem, and it lies in the fact that for this construction to hold, we need the Lagrangian not to change convexity. Let me write what I know about the Legendre transformation, in a somewhat formal way:
Given a function $f: x\rightarrow f(x)$, we define the function $p: x\rightarrow p(x)$ by the relation $\frac{df}{dx} = p$. Supposing $\frac{df}{dx}$ is invertible, we can define the inverse of $p(x)$, which we call $g : p\rightarrow g(p)$. Then, the legendre transformation of $f$ is $f^* : p\rightarrow f^*(p)$ such that $\frac{df^*}{dp}=g(p)$. We can write, in a more familiar way, $g(p) = x(p)$ since it is the inverse of $p(x)$.
Anyway, we can prove with those assumption that $f^* = pg(p)-f(g(p))$ which is $f^* = px-f(x)$ written in the "familiar" way. All that is just to point out that, for all this construction to work, and hence for the existence of $f^*$, we need the condition that $f(x)$ be of constant convexity, otherwise $\frac{df}{dx}$ is not invertible and we cannot even define $g(p)$.
However, when we consider a general Lagrangian, I don't think that this is always the case. Taking simply $L = \dot{q}^3$ makes the Lagrangian not of constant convexity. And yet, we always use the Hamiltonian, without ever checking this convexity constraint. Why can we do this? Is it because we are interested in the local behavior of our Lagrangian? But even then, what would we do at an inflexion point? 
Or is it because a general "physical" Lagrangian will always satisfy the condition of constant convexity?
 A: This is a good but quite broad question. Let us suppress position dependence $q^i$, $i\in\{1, \ldots, n\}$, and explicit time dependence $t$ in the following to keep the notation simple.
Given a Lagrangian $L(v)$, several things could go wrong if we try to perform a Legendre transformation in order to construct a Hamiltonian $H(p)$. Define for later convenience the function
$$  h(v,p)~:=~p_j v^j -L(v). \tag{0} $$
As explained on the Wikipedia page, there are at least two definitions of Legendre transform:
$$  H(p)~:=~ \sup_v h(v,p) ,\tag{1}$$
and
$$\begin{align} g_j(v)~:=~&\frac{\partial L(v)}{\partial v^j}, \qquad f~:=~ g^{-1} , \cr H(p)~:=~&h(f(p),p)~=~p_i f^i(p) -L\circ f(p).\end{align}\tag{2}$$
The former definition 1 (which is the so-called Legendre-Fenchel transform) tends to work better for convex (possibly non-differentiable) Lagrangians $L$, while the latter definition 2 (which is historically the original Legendre transform) tends to work better for differentiable (possibly non-convex) Lagrangians $L$. But in general we need to impose more conditions, as becomes clear below. (Needless to say that these conditions may be violated in actual systems.)
Concerning the former definition 1, see also this, this Phys.SE posts, and this Math.SE post. Works in rigorous mathematical/statistical physics seem to prefer definition 1. In classical mechanics & field theory, we are traditionally using the latter definition 2, which we will concentrate on from now on in this answer.
For technical reasons, one often imposes a regularity condition that the $n\times n$ Hessian matrix$^1$
$$H_{ij}~:=~\frac{\partial g_j(v)}{\partial v^i}~=~\frac{\partial^2 L(v)}{\partial v^i\partial v^j} \tag{3}$$
has constant rank $r$.
If the rank $r=n$ is maximal, the inverse function theorem guarantees the local (but not the global) existence of an inverse function $f$.
If a globally defined inverse function $f$ exists, then the construction of the Hamiltonian $H(p)$ was discussed in this Phys.SE post.
If the rank $r<n$ is not maximal, then the Legendre transformation is singular. Then we cannot express all the velocities $v^i$ as functions of momenta $p_j$, only $r$ thereof. This leads to $n-r$ primary constraints. It turns out that formally in this singular case $r<n$, it is still possible to locally construct a Hamiltonian in an extended phase space such that the Legendre transformation is an involution. See e.g. my Phys.SE answer here and references therein.
Finally, we should mentioned that even if we can mathematically define the Legendre transform $H(p)$, there is no guarantee that it makes sense physically. E.g. in QM we usually require that the Hamiltonian operator $\hat{H}$ is self-adjoint and bounded from below.
References:

*

*Hugo Touchette, Legendre-Fenchel transforms in a nutshell, 2005.

--
$^1$ Incidentally, OP's example
$$L(v)~=~\frac{1}{3}v^3\tag{4}$$
violates the constant rank condition (3). For this example definition 1 yields
$$ H(p)~=~ \infty,\tag{5}$$
while definition 2 yields a double-valued Hamiltonian
$$\begin{align}g(v)~=~&v^2,\qquad f(p)~=~\pm \sqrt{p}, \cr 
H(p)~=~&\pm\frac{2}{3}p^{\frac{3}{2}}, \qquad p~\geq~ 0.\end{align}\tag{6}$$
It seems that in order to have a viable physical model, one should discard the negative branch.
