Unlocking an O2 Iphone
I have tried one of those sites in 2010 to unlock my iPhone 4 (SFR), it worked perfectly and I'm still using it. I think that these types of websites have people with access to Apple databases and can easily unlock it from there. I can't think of another way to unlock your phone without going through the original carrier, Apple or these websites. You can still change the mother board but that's like changing the phone. 

There are jailbreak methods you may want to check iClarified they'll tell how and if you can do it.