Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda_2(B)>0$. The statement in the OP     

> If $\|A-B\|<\lambda_2(B)$, then $\lambda_2(A)>0,$

is a consequence of the "eigenvalue stability" inequality 
$$|\lambda_i(A)-\lambda_i(B)|\leq \|A-B\|,$$
which is proven, for example, in <A HREF="https://terrytao.wordpress.com/2010/01/12/254a-notes-3a-eigenvalues-and-sums-of-hermitian-matrices/">Tao's notes</A> (equation 13).