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.