My solution for $n=3$ (upon Suvrit's request):

To begin with, we solve $A+A^T=M$ together with $A{\bf1}={\bf1}$ (no inequality for the moment). This is a linear system in $A$, which consists in $9$ equations in $9$ unknowns. However, it is not Cramer, because the set of skew-symmetric matrices $B$ such that $B{\bf1}=0$ is one-dimensional, spanned by
$$\begin{pmatrix} 0 & 1 & -1 \\\\ -1 & 0 & 1 \\\\ 1 & -1 & 0 \end{pmatrix}.$$
In particular, there is a condition for solvability in $A$, but this condition is met by the assumption that $\sum_{i,j}m_{ij}=6$.
Notice that $a_{ii}=\frac12m_{ii}$.

Thus there is a solution $A$, and every solution is of the form $A+aB$. There remains to find $a$ so as to satisfy the inequality $A+aB\ge0_n$. For this, let us denote $\mu$ the lower  bound of $(a_{12},a_{23},a_{31})$, and $\nu$ that of $(a_{21},a_{13},a_{32})$. 

**Claim**: we have  $\nu+\mu\ge0$. This inequality allow us to find an $a$ such that $a_{12}+a,a_{23}+a,a_{31}+a,a_{21}-a,a_{13}-a,a_{32}-a\ge0$, which solves the problem.

Proof of the claim:  we have $a_{12}+a_{21}=m_{12}\ge0$, $a_{12}+a_{13}=1-\frac12m_{11}\ge0$ because of the assumption that $m_{ij}\le2$, and finally
$$a_{12}+a_{32}=a_{12}+a_{21}+a_{32}+a_{23}-a_{21}-a_{23}=m_{12}+m_{23}+\frac12m_{22}-1.$$
Form the assumption, this is equal to
$$2-m_{13}-\frac12(m_{11}+m_{33})\ge0.$$
Finally, every sum $a_{ij}+a_{ji}$, $a_{ij}+a_{ik}$ and $a_{ij}+a_{kj}$ of elements of both sets is non-negative, hence $\mu+\nu\ge0$. Q.E.D.

Adapting this proof to higher $n$ seems difficult, because the kernel of the linear system the  set of skew-symmetric matrices $B$ such that $B{\bf1}=0$) has dimension $\frac12(n-1)(n-2)$.