Here is the proof using the alternative route. I'll post a direct proof with the estimates for binomial coefficients later.

Let $X$, $Y$ be two 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.

More later.