The random-matrix connection is a bit of a red herring: 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 Tao's notes (equation 13).