It shouldn't be that hard. A million dollars, a few people who know about RF hardware, and the (possibly leaked) GSM specs should be enough.
There might be some trouble with encryption / carrier's private keys, but I think that shouldn't be an issue, since a multiband GSM phone works with every strange operator in every remote country, as long as the frequency is supported.
Some cool applications for a really free GSM from the top of my head:
- Virtual SIMS, you only use the data from the SIM, not the physical card to login. (Might be tricky because the SIM protects its information. If you don't want to resort to attacks ala chip shaving and electron microscopes to get the keys, you might just setup a simless private network with a DIY SIM tower (that already exist, AFAIK), as a kind of proof-of-concept.)
- You can see when you recieve a silent SMS ("type 0"), that authorities use to ping your phone to trace you. You can also send them.
- You can record audio from and play it to the phone, which is not possible in most consumer phones
- You can implement hardware encryption (which is tricky for voice, since GSM uses psychoaccoustical compression techniques that might not work on a encrypted stream - nevertheless this is a solved problem and there should be papers on this)
- You would find a bunch of security holes in the network, since its been relying on obscurity and trusted devices for so long.
- You could have a phone that's bottom to top trusted and open-source.