I was wondering whether, for a given finite-dimensional manifold, the connection $\nabla$ exists and is uniquely defined?
Afais for Riemannian manifolds, there exists always exactly one Levi-Civita connection, but the calculation is rather cumbersome.
Now, if we consider manifolds without a metric, is there still always one connection (now we do not require torsion-freeness and compatibility with the metric, of course)?
Without assumption of compatibility with metric and vanishing torsion connection is never unique; once you choose local coordinates, connection coefficients in these coordinates can be chosen arbitrarily. It's demanding of vanishing torsion and compatibility with the metric that fixes them on Riemannian manifold. Notice that given Riemannian manifold you can often choose different metric on it and that will yield different connection.