I'm usually on 3G most of the time. And I back up to iTunes not iCloud. Mmm
Since you said you already setup the phone as new here is what I would say you could try. Try doing a SIM swap call up your carrier and ask for a new SIM and for them to kill your current SIM and activate the new one. If that doesn't do anything try turning off your data while you're at home it wont affect your phone reception as in calls but unless you have Wifi you wont have internet. When I was in the US and roaming on the AT&T network my battery turned into mush. So you just want to see if poor reception that is making your battery suffer. You can turn it off by going Settings ->General ->Cellular and flip Cellular Data to off. When you're ready to test charge up the phone to full charge and you have to turn it off for a good length of time like 3 or 4 hours. If that doesn't do anything try this
Hook up your iPhone to iTunes
Go through each tab except the Apps and uncheck the sync option and perform a sync
This will remove all the media on your iPhone
Reboot the iPhone
Screenshot your homescreen and all the open folders to remember your apps installed
Then delete any apps that don't require an effort to re-install (passwords, usernames, etc)
Plug the power cable in to charge and then power the phone off and leave it charging for like four hours or so
Then use the phone in that state and see if the battery improves
After a couple hours of use hook it up to iTunes and then go into each tab and set the sync option to put all the media back on the iPhone
Re-install whatever apps you removed
Reboot
*my personal opinion*
I found I had slightly better battery life when I stopped quiting apps through the task switcher. What I do now is kill apps that I only use periodically or that I know use a lot of memory. So for example a FollowFriday Generator which I only use on Friday, Facebook and Mobiel Safari use lots of memory.