Let $a,b \in \mathbb Z$. Prove that if $3 \mid (a+2b)$ then $3 \mid (2a+b)$

$3|a+2b$ then $3|2a+4b$ then $3|2a+4b-3b = 2a+b$.

Of course, you can also reverse this. If $3|2a+b$ then $3|2a+4b = 2(a+2b)$ Now use Euclid lemma and we have $3|a+2b$.

Since $a-3m=-2b$, $a+m = 4m-2b = 2(2m-b)$ which is even and thus is divisible by two. Both of your solutions work, but the first one is cleaner since it does not involve the division by two.

Let me actually address your question rather than just giving an answer. Both solutions work. For the second one:

when - instead of solving for $a$, I solve for $b$, then I get this:
$2a+b = 3 \frac{a+m}{2}$
How can I even be sure that this number is an integer?

To complete the argument, notice that $2a + b$ is an integer (obviously); therefore, $3 \frac{a + m}{2}$ is an integer. And because it's an integer, $\frac{a + m}{2}$ must be an integer (since $3$ does not cancel $2$). This means that it is a multiple of $3$.