Wireless network virtualization enables mobile virtual network operators (MVNOs) to develop new services on a low-cost platform by leasing virtual resources from mobile network owners. In this paper, we investigate a two-stage spectrum leasing framework, where an MVNO acquires spectrum resources through both advance reservation and on-demand request. To maximize its surplus, the MVNO needs to jointly optimize the amount of spectrum resources to lease in the two stages by taking into account traffic intensity, random user locations, wireless channel statistics, quality-of-service requirements, and the price differences. Meanwhile, to maximize the utilization of the acquired resources, the MVNO dynamically allocates the spectrum resources to its mobile subscribers (users) according to fast wireless channel fading. We formulate the MVNO's surplus maximization problem as a tri-level nested optimization problem consisting of dynamic resource allocation (DRA), on-demand request, and advance reservation subproblems. To solve the problem efficiently, we first analyze the DRA problem, and then use the optimal solution to find the optimal leasing decisions in the two stages. In particular, we derive a closed-form expression of the optimal on-demand request, and develop a stochastic gradient descent algorithm to find the optimal advance reservation. For a special case when the proportional fairness utility function is adopted, we show that the optimal two-stage leasing scheme is related to the number of users and is irrelevant to user locations. Simulation results show that the two-stage spectrum leasing scheme can adapt to different levels of traffic and on-demand price variations, and achieve higher surplus than conventional one-stage leasing schemes.