What does it mean "being geodesic" is not invariant? We know that "being geodesic" is not invariant under re-parametrization. Only affine re-parametrization preserves the property of being a geodesic. Also, a geodesic is locally distance minimizer.

My question is
Let $\alpha(s)$ be a geodesic on a manifold $M$, if we parametrize it to be $\beta(t)$ where $t=t(s)$ is not affine. The curve $\beta$ is not a geodesic and hence is not minimizer!!!  
Geometrically they represent the same curve on $M$ and the metric is the same, why one of them is minimizer and the second is not. I know the proofs and the properties, I want to interpret it geometrically and imagine why the same curve and the same metric gives a minimizer one time and a non-minimizer second time I am really confused.  
 A: The question is - a minimizer of what? There are two different important notions involved - the length and the energy of a smooth curve. The length of a curve $\gamma \colon [a,b] \rightarrow (M,g)$ in a Riemannian manifold is defined as
$$ L(\gamma) := \int_a^b ||\dot{\gamma}(t)||_{\gamma(t)} \, dt $$
while the energy of a curve is defined as
$$ E(\gamma) := \frac{1}{2} \int_a^b ||\dot{\gamma}(t)||_{\gamma(t)}^2 \, dt. $$
The length functional is invariant under reparametrization and hence if you have one minimizer, you have infinitely many - a minimizer of length does not come with a "preferred" parametrization. The energy functional is not invariant under reparametrization. For example, if $\gamma_1 \colon [0,1] \rightarrow \mathbb{R}^2$ is given by $\gamma_1(t) = (t,0)$ while $\gamma_2 \colon [0,1] \rightarrow \mathbb{R}^2$ is given by $\gamma_2(t) = (t^2, 0)$, then $\gamma_2$ is a reparametrization of $\gamma_1$, they have the same trace and length, but $E(\gamma_1) = \frac{1}{2}$ while $E(\gamma_2) = \frac{2}{3}$. (Strictly speaking, this is usually not considered a legal reparametrization, but it's not really relevant for this discussion).
You can think of $E(\gamma)$ as a measure of the "total kinetic energy" of a particle traveling along $\gamma$ with the speed $||\dot{\gamma}(t)||$. The particle traveling along $\gamma_1$ travelled with constant speed while the particle traveling along $\gamma_2$ started from rest (zero velocity) and experienced acceleration ("force") in order to travel the same distance during the same time resulting in a higher total kinetic energy. 
A geodesic is a curve that satisfies $\nabla_{\dot{\gamma}(t)} \dot{\gamma}(t) = 0$, that is, a curve with zero acceleration. Note that this condition is not invariant under arbitrary reparametrization. By replacing $\gamma$ with $\gamma(\varphi(t))$, you change the acceleration of the curve. With this definition, one shows that a geodesic must be a curve with constant speed and that it locally minimizes length. Hence, not all the curves that minimize length satisfy the geodesic equation - they must also have constant speed parametrization. 
However, one can show that a curve with a minimal "total kinetic energy" among all curves connecting two points must in fact be length minimizing geodesic and in particular a constant speed curve. On the other hand, a geodesic is locally energy minimizing. Hence, geodesics are precisely the curves that locally minimize energy, not length. The curve $\gamma_1$ from the discussion above is a geodesic because it minimizes the energy, while $\gamma_2$ is not geodesic because it doesn't minimize the energy (even locally) nor it has zero acceleration. For details and proofs, see Chapter 5 of Petersen's Riemannian Geometry.
There are many reasons why one prefers to think about geodesics as constant speed parametrized curves and not as curves that locally minimize length with an arbitrary parametrization. For one, the statement that a geodesic is determined by a starting point and a velocity vector obviously holds only if the geodesic has a constant speed parametrization.
A: Let me define trajectories $x$ satisfying the equation $\nabla_{\dot{x}(\lambda)}\dot{x}=0$, autoparallels. This equation is not reparametrization invariant. On the other hand, let me define geodesics to be curves between two points with minimal length. As the OP remarks, this notion should be reparametrization invariant. We conclude that, with these definitions, geodesics are not equivalent to autoparallels.
In order to obtain an equation for a geodesic, one needs to minimize the first action of levap's answer. One can use the Euler-Lagrange equations for example. The solution can be put in a form which resembles the autoparallel equation up to a term that ensures reparametrization invariance
$$0=\ddot{x}^\mu+\dot{x}^\alpha\Gamma^\mu_{\alpha\beta}\dot{x}^\beta-\dot{x}^\mu\frac{d}{d\lambda}\log\left(\sqrt{g_{\alpha\beta}\dot{x}^\alpha\dot{x}^\beta}\right).$$
It is simple to check that this equation is indeed reparametrization invariant and, if $x$ is parametrized by an affine parameter, where $g_{\alpha\beta}\dot{x}^\alpha\dot{x}^\beta$ is constant, it reduces to the autoparallel equation.
