I think you have it backwards. What would happen if car companies also owned the roads, and each brand of car could only be driven on the corresponding roads?
At the moment, those are the options on the table -- throwing our mobile infrtastructure out and starting over with a clean slate is not something practically achievable.
No, it isn't. It's why infrastructure is usually owned by government, or given protected monopoly status. Where infrastructure is defined as anything too expensive to build redundantly (starting with the military and its natural monopoly, which we call government).
Your wireless coverage is not affordable because you are paying to build 75% of each of three redundant mobile phone networks. Independent networks would never exist in a free market - only the FCC licensing process brought them about. And despite that, the vacuum is so strong it produced several mergers so far (Cingular + ATT, Sprint + Nextel, and of course, the remerger of the bells into Verizon and SBC/ATT).
Taking the infrastructure into government control is political suicide, no one is going to do it. I'm not interested in giving a protected monopoly without a stronger interpretation of anti-trust law similar to United States v. Paramount Pictures, Inc.
Specifically, a company with a natural monopoly on distribution (wireless, cable, POTS, or fiber telecom companies) should not be able to operate or have exclusivity deals with companies in production or exhibition markets. No Sprint only phones and no Comcast owned television channels, or I'll do everything in my power to at least make sure they have plenty of healthy competitors who can keep them in check, even if it means I pay a premium.
During the early 90's many telecom companies either had protected monopoly status or were government owned. Neither worked well, because disruptive technology meant that they were undercut in price by newer competitors which were also able to offer new, innovative services that the incumbents could not - or would not - match.
Cellular network infrastructure isn't like roads, pipes or train tracks where you build it and then maintain it forever. It requires constant investment in new technology, and it isn't at all clear to me that government ownership of protected monopoly status would be beneficial to the consumer.
Now, coverage in some highly-populated areas is bandwidth-limited. In other words, there are often enough customers of each carrier in a place to saturate the corresponding antennas. But any time the T-mobile antenna is not saturated and the AT&T antenna is over capacity, there is waste. This waste shows up on both our bills (forgive me for assuming you're a T-mobile customer for the sake of argument).
Obviously, competition is a good thing, but its benefits are easily overwhelmed by infrastructure costs. Electric utilities generally operate very efficiently with government-sanctioned monopolies (and subsidies). The trading requirements enacted in the late '90s to promote "competition" on the grid are widely considered to have failed to improve utility service, and are implicated in things like the 2001 California energy crisis. Since colonial times, the Crown granted molopolies for expensive things like colonizing India...
Edit: Yes, I mentioned them twice.