I had the same problem with my iPhone 4 (not 4S) and I thought it was the battery at first but a new battery didn't fix it. I spent hours and hours looking for a solution and tried everything. The phone was out of warranty so I had to get my hands dirty and take the risk and changing the parts myself. A new charging cable didn't help either. Then I changed the Dock connector and the issue was sorted. Please follow these steps. Buy the following parts:
1) iPhone 4 Original Black Replacement Complete Dock Connector (microphone, charging port, home button) - mendmyi
2) ORIGINAL APPLE IPHONE 4 4th 4G (16GB/32GB/64GB) INTERNAL BATTERY REPLACEMENT
3) Screwdriver Set for iPhone 3 3G 4 4G iPad Nintendo DS PSP
I think all in all cost me about £30+. I bought the battery just in case it was the battery and I was desperate to get the phone working. By the way I bought a new set of tools as I read that the ones that come with the parts are useless. I used the following YouTube video to change the dock connector - it took me about 15 minutes to change it and a bit of patience! I didn't use a wrist band to earth any static - you should be fine without one.
Changing the iPhone 4 dock connector
The tricky bit is reconnecting the Home button points and removing the rubber casing from the existing mic to the new dock. A pair of tweezers like she mentions in the video is also worth getting hold of. I didn't use one, but wished I had one when I was reconnecting the Home button!
I remember I dropped it a couple of times (inside the case). It is said that the connector is very sensitive to water so keep it away from water! After changing the parts its like new!
Hope this helps and it will save you lots of money! At your own risk!