We consider an underlay coexistence scenario where secondary users (SUs) must keep their interference to the primary users (PUs) under control. However, the channel gains from the PUs to the SUs are uncertain due to a lack of cooperation between the PUs and the SUs. Under this circumstance, it is preferable to allow the interference threshold of each PU to be violated occasionally as long as such violation stays below a probability. In this article, we employ Chance-Constrained Programming (CCP) to exploit this idea of occasional interference threshold violation. We assume the uncertain channel gains are only known by their mean and covariance. These quantities are slow-changing and easy to estimate. Our main contribution is to introduce a novel and powerful mathematical tool called Exact Conic Reformulation (ECR), which reformulates the intractable chance constraints into tractable convex constraints. Further, ECR guarantees an equivalent reformulation from linear chance constraints into deterministic conic constraints without the limitations associated with Bernstein Approximation, on which our research community has been fixated on for years. Through extensive simulations, we show that our proposed solution offers a significant improvement over existing approaches in terms of performance and ability to handle channel correlations (where Bernstein Approximation is no longer applicable).