I don't believe that it needs someone new or less evil (or even that google is necessarily less evil), it just needs someone who wants that market.
As soon as someone makes a play for it, the others have to join in.

Becasue if they have the bandwidth to give it to you, and need the market, they will.
A year ago in the UK, I couldn't get a decent practical 3G data service (no problem with phone service) at a price I could afford.
A few months back, one of the telcos decided they wanted that market and started offers for it, now mobile bandwidth has jumped 7 fold, and I can get gigs of data transfer for very little money. In fact, for the same cost as my ISP I can get half the data transfer as my adsl line, at what is an acceptable speed (certainly faster than anything I had up until a few years ago). This is nothing I could have done before, and I think it is fantastic - I have a functional mobile internet that works wherever I want to go, and it can only get better as more of the telcos have to join in. They have to work hard in the UK - it is a very mature market and noone who wants a phone doesn't have one and we change our phones a lot. The only new business they can get is taking it off each other.

Well, regardless whether it is 3/4/x/G phone, or WiMax/TLE/WTF etc, the technology is available, but if you have a problem with people providing the service, there is nothing you can do about it. If they think they can get money out of you they will.