Due to emerging mobile applications and an Internet of things, data traffic carried by wireless networks has increased dramatically. As a result, maximizing the utilization of the limited network resource is a top priority. To date, there exists a large body of work on the stochastic network utility maximization (NUM) problem. On the one hand, the stochastic NUM problem and its associated solutions have been mainly investigated under the light-tailed (LT) data condition. On the other hand, empirical results show that data delivered by wireless networks is not only large in volume but also highly variable, which can be characterized by heavy-tailed (HT) distributions. Such HT traffic exhibits high burstiness and strong temporal correlations, which are fundamentally different from the behavior of LT traffic. In this paper, first it is shown that the classic stochastic gradient algorithms (SGAs), as effective solutions for stochastic NUM problems, fail to prevent HT traffic flows from aggressively competing with LT flows for limited resources. This leads to unbounded queueing delay for LT flows, which results in network instability. To counter such a challenge, the time-average stochastic gradient routing algorithm (TA-SGRA) is proposed, which prevents competition among HT and LT traffic flows so that utility optimality and network stability can be achieved simultaneously. Moreover, because HT data has unbounded moments, such as mean and variance, it is not feasible to apply the conventional convergence analysis, which assumes the moment boundedness of traffic arrivals. To address this problem, the ordinary differential equation (ODE) method is adopted to prove that the proposed algorithm still converges even with highly variable HT traffic. Comprehensive simulation results are shown to verify the derived theoretical results.