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.
