Firstly, networks should become completely device-agnostic. Phones and their financing should be separated from the networks. Long-term contracts and the financing deals on phones basically function as an installment scheme for the phone itself, so unbundle this from the contract. The retail outlets could then sell unlocked phones for any network. In some countries (e.g. USA) this may cause headaches for your competitors, but that's partly the point.
Secondly, charge customers for what they use. Charge per kilobyte. Make as little distinction as possible between voice, GPRS, SMS, or MMS traffic. Pass on charges from traffic to other mobile operators directly, and itemize the charges separately on the statements.
In doing this, the operator transforms into a bulk supplier of bandwidth as a commodity.
An operator could do the sums as follows: the operating costs of the network, plus payments for infrastructure, plus needed funds for planned expansion, gives a monthly figure.
My completely uninformed bet is that this figure, divided by the total kilobytes per user per month, plus a 50% margin would still be much, much lower than the current call rates for most mobile users. By pulling the floor out of the mobile market, customers would migrate in droves.
Doing this would also trigger the mother of all price wars. However, as the first to adopt the model, the operator gets the jump on the competition and should, adequately managed, remain a couple of iterations ahead of the rest.
The benefit in doing this is not just to the company that grabs market share, but to society in general. Mobile devices no longer need to be phones but could also be AR, telemetry, or whatever. Device manufacturers and developers should be able to roll out new products and services as easily as they can on the Internet, and the mobile network would become the infrastructural foundation for the next evolutionary step in the information revolution, a leap in the level of interconnectedness, and the fabled "Internet of things". But first they need to get out of the way of their own business model.