Geodesics: From Affine Connection to Length Minimisation On a manifold $M$ with affine connection $\nabla$, I can define a geodesic as a special integral curve. Namely a geodesic is an integral curve $\gamma$, generated by a vector field $X$, that also parallel transports this tangent vector i.e. it satisfies
$$\tag{$\star$}\nabla_v v =0$$
Note that we are able to define the geodesic without any mention of a metric at all
Q1: does this mean geodesics exist on non-Riemannian manifolds?
Q2: how can I start with the definition $(\star)$, introduce a metric tensor $g$ and show that the geodesic will be the curve that minimises arclength. Everything I read assumes that the connection is the affine connection. I am aware that the metric picks out the affine connection as the only metric compatible connection (satisfying $\nabla g=0$) but that doesn't mean other connections don't exist. Supposing $(\star)$ was defined with respect to a different connection, what happens?
 A: Q1. Like you say, any connection $\nabla$ on a smooth manifold $M$ determines a set of geodesics without any need for a metric. We call the structure $(M, \nabla)$ an affine manifold.
Q2. For most connections $\nabla$ there is no metric $g$ whose geodesics coincide with those $\nabla$.
On the other hand, for any connection $\nabla$ there is a unique torsion-free connection $\nabla'$ with the same geodesics, so we may as well restrict our attention to torsion-free connections. (In terms of the Christoffel symbols, the new connection is given by $(\Gamma')_{ab}^c = \frac{1}{2}(\Gamma_{ab}^c + \Gamma_{ba}^c$).)
Now, any connection $\nabla$ is specified locally by its Christoffel symbols, and for a torsion-free connection $\nabla$, we have $\Gamma_{ba}^c = \Gamma_{ab}^c$, so a connection is given in local coordinates by $\frac{1}{2} n^2 (n + 1)$ functions, where $n := \dim M$. But a metric is specified in local coordinates by $\frac{1}{2} n (n + 1)$ functions, so, informally, for $n > 1$ there are many more connections than metrics.
Put another way, the map $$\mathcal C : \{\textrm{metrics on $M$}\} \to \{\textrm{torsion-free affine connections on $M$}\}$$ that assigns to a metric $g$ on $M$ its Levi-Civita connection $\nabla^g$ is not surjective. In fact, it is not injective either; for a typical Levi-Civita connection $\nabla^g$ the only metrics whose geodesics are those of $\nabla^g$ are those homothetic to $g$, that is, the metrics $\lambda g$, $\lambda > 0$, but for some metrics there are others (e.g., all of the metrics $g_{ij} \, dx^i \,dx^j$ on $\Bbb R^n$ with $g_{ij}$ constant have the same geodesics as the standard Euclidean metric, $g_{ij} = \delta_{ij}$).
Remark One can ask how to determine for a given torsion-free connection $\nabla$ whether it is the Levi-Civita connection of some metric. A partial answer is provided by various tensorial obstructions to metrizability, that is, tensors defined invariantly in terms of $\nabla$ that vanish if $\nabla$ is a Levi-Civita connection. The simplest of these is the trace $Q_{ab} := R_{ab}{}^c{}_c \in \Gamma(\bigwedge^2 T^* M)$ of the curvature over the last two indices, that is, the section
$$Q(X, Y) = \operatorname{tr}(Z \mapsto R(X, Y) Z) = \sum_{i=1}^n e^i (R(X, Y) E_i),$$ where $(E_i)$ is some local frame and $(e^i)$ is its dual coframe. This quantity vanishes iff $\nabla$ (locally) preserves some volume form---and any Levi-Civita connection $\nabla^g$ preserves any local volume form for $g$---but a generic connection has $Q \neq 0$ and so preserves no volume form locally. This obstruction is not sharp, that is, there are connections for which $Q = 0$ but which are not Levi-Civita connections. One can construct other, more sophisticated (and sensitive) obstructions.
A: You can use such definition without using a metric, for example see the notion of affine manifold, like the quotient of $\mathbb{R}^n-\{0\}$ by the homothetic map $h(x)=2x$, it is endowed with a connection inherited from the classical flat connection of $\mathbb{R}^n-\{0\}$ since that connection is preserved by $h(x)=2x$.
Geodesic can be defined in Riemannian geometry with the distance. A Riemannian metric on $M$ induces a distance and if $M$ is complete, a geodesic between $x,y$ with will be the path between $x$ and $y$ which is the critical point of function. See the answer here.
Shortest path to a geodesic
A: Given a metric $g$, the Levi-Civita connexion is the unique connexion which satisfy two further conditions : first, $\nabla g =0$, then its torsion is $0$.
These two condition are needed to prove that geodesics "minimize" distance in they satisfy Euler Lagrange equation for the Lagrangian $\int g(\gamma '(t), \gamma '(t)) dt$.
