Let $\nabla$ be a linear connection on $M$, let $\{e_i\}$ be a local frame on some open subset $U \subset M$, and let $\{\omega^i\}$ be the dual coframe. We know that there is a uniquely determined matrix of 1-forms $\Theta^i_j$ on $U$, called the connection 1-forms, for this frame, such that $$ \nabla_X e_i = X\lrcorner \Theta^j_i e_j $$ for all $X \in T M$.
There is a well knon formula called Cartan’s first structure equation: $$d\omega^k = \omega^i \wedge \Theta^k_i + \tau^k,$$ where $\{\tau^1 , . . . , \tau^n\}$ are the torsion 2-forms, i.e., $\tau^k$ is the $k$th component of $$ \tau (u, v)= \nabla_u v- \nabla_v u-[u,v] $$
So according to this, if we know the torsion, can we recover the connection (the matrix $\Theta$) by computing the structure functions ($T_{ij}^k$ such that $d\omega^k=\sum_{i<j}T_{ij}^k\omega^i \wedge\omega^j$)?
I know that this is done in some examples, mainly with the Levi-Civita connection of a Riemannian metric and orthonormal frames. In this case there is torsion 0, and moreover the matrix is antisymmetric. But can this always be done?
No, you can't determine the connection just from the torsion.
The space of linear connections on a given manifold $M$ is an affine space whose associated translation space is the space of type $(1,2)$-tensor fields on $M$. This means that given any two connections $\nabla,\nabla'$ on $M$, then $\nabla'-\nabla$ is a type $(1,2)$-tensor field, and if $\nabla$ is a connection and $A$ is a type $(1,2)$-tensor field, then $\nabla+A$ is a connection.
So, fix a connection $\nabla$ and a such a tensor $A$. Compute:
$$\begin{align}\tau^{\nabla+A}(X,Y) &= (\nabla+A)_XY - (\nabla+A)_YX - [X,Y] \\ &= \nabla_XY+A_XY-\nabla_YX-A_YX-[X,Y] \\ &= \tau^\nabla(X,Y) + A_XY-A_YX.\end{align}$$This means that $\nabla+A$ and $\nabla$ have the same torsion whenever $A$ is symmetric in the sense that $A_XY=A_YX$, for all vector fields $X$ and $Y$.