Here is the proof using the alternative route. 

Let $X$, $Y$ be two independent real-valued random variables such that $EX,EY\ge 0$ and $\min(E|X|,E|Y|)=I$. We want to prove that $E|X+Y|\ge I$. Again, as in both the OP and Iosif's post, we can consider only the case when $X$ is $A$ with probability $P$ and $-B$ with probability $Q$, while $Y$ is $a$ with probability $p$ and $-b$ with probability $q$, where $A,B,a,b\ge 0$.

Then we need to show that the inequality
$$
(A+a)Pp+|a-B|pQ+|b-A|Pq+(B+b)Qq<I
$$
is impossible. So suppose it holds.

If we estimate each absolute value by what is inside it, we get
$$
(A+a)Pp+(a-B)pQ+(b-A)Pq+(B+b)Qq
\\
=(ap+bq)+(AP-BQ)(p-q)
\\=E|Y|+(EX)(p-q)<I\,,
$$
which is possible only if $p<q$.
By symmetry, we conclude that we must also have $P<Q$.

Now estimate $|a-B|\ge a-B$ and $|b-A|\ge A-b$. We obtain 
$$
(A+a)Pp+(a-B)pQ+(A-b)Pq+(B+b)Qq
\\
=(AP+ap)+BQ(q-p)+bq(Q-P)<I\,.
$$
However, the last two terms are nonnegative and the condition $0\le EX=AP-BQ$ implies that $AP\ge \frac 12[AP+BQ]=\frac 12E|X|\ge\frac 12I$ and similarly for $ap$, so we run into a contradiction.

*Edit* Here is the direct binomial coefficient approach. I'll start where Iosif stopped though I'll denote by $A$ what he denotes by $A/p$, etc.

We need the inequality 
$$
\sum_{k=0}^n{n\choose k}p^kq^{n-k}|Ak-B(n-k)|\ge Ap+Bq
$$
Fix $A+B=1$ and consider the difference as a function of $A\in[0,1]$. It is piecewise linear, so the minimum is attained at a zero of some absolute value. Clearly, the endpoints (when the random variable preserves sign) are not competitors, so it is enough to consider the case when $A=\frac{n-\ell}n, B=\frac{\ell}n$, $0<\ell<n$. Then all the absolute values except the vanishing one for $k=\ell$ are at least $A+B=1$, so the LHS is at least
$
1-{n\choose \ell}p^\ell q^{n-\ell}
$
and we want to show that
$$
1-{n\choose \ell}p^\ell q^{n-\ell}\ge Ap+Bq\,,
$$
i.e.,
$$
Aq+Bp\ge {n\choose \ell} p^{\ell}q^{n-\ell}
$$ 
Since $Aq+Bp\ge q^Ap^B=p^{\frac{\ell}{n}}q^{\frac{n-\ell}{n}}$, it suffices to check that
$$
{n\choose \ell} [p^{\ell}q^{n-\ell}]^{1-\frac 1n}\le 1\,.
$$
The product in brackets is maximized when $p=\frac \ell n$, $q=\frac{n-\ell}{n}$, so we want 
$$
{n\choose \ell}[(\tfrac{\ell}n)^{\ell}(\tfrac{n-\ell}n)^{n-\ell}]^{1-\frac 1n}\le 1\,.
$$
Now the LHS can be rewritten as $\frac{n}{\ell^{\frac \ell n}(n-\ell)^{\frac{n-\ell}n}}U$ where 
$$
U={n-1\choose \ell-1}(\tfrac{\ell}n)^{\ell-1}(\tfrac{n-\ell}n)^{n-\ell}={n-1\choose \ell}(\tfrac{\ell}n)^{\ell}(\tfrac{n-\ell}n)^{n-\ell-1}
$$
Since $U$ appears as two equal terms in the binomial expansion of 
$
[\tfrac{\ell}{n}+\tfrac{n-\ell}n]^{n-1}\,,
$
we must have $U\le \frac 12$. On the other hand, $\frac 1{\alpha^\alpha\beta^\beta}\le 2$ for $\alpha,\beta>0, \alpha+\beta=1$, and we are done again.

It would be interesting to see what factor on the right hand side can be put in place of $1$ for $n\ge 3$. I suspect that the worst case for even $n$ is addition of $n$ Rademacher independent random variables ($\pm 1$ with probability $\frac 12$ each) even if we allow them to be different (but with expectations of the same sign) but I have no proof of it at the moment. The odd case may have a rather ugly answer even for $n=3$.