Regulatory genes called small RNAs (sRNAs) are known to play critical roles in cellular responses to changing environments. For several sRNAs, regulation is effected by coupled stoichiometric degradation with messenger RNAs (mRNAs). The nonlinearity inherent in this regulatory scheme indicates that exact analytical solutions for the corresponding stochastic models are intractable. Here, we present a variational approach to analyze a well-studied stochastic model for regulation by sRNAs via coupled degradation. The proposed approach is efficient and provides accurate estimates of mean mRNA levels as well as higher-order terms. Results from the variational ansatz are in excellent agreement with data from stochastic simulations for a wide range of parameters, including regions of parameter space where mean-field approaches break down. The proposed approach can be applied for quantitative modeling of stochastic gene expression in complex regulatory networks.