It sounds like the battery or 30-pin is at fault.
First, change the battery. This will solve a good chunk of these problems. You can find the guide and part here.
If this doesn't fix the problem, the 30-pin is worn out on the iPod. This can be replaced, but you need to be patient. It isn't for the feint of heart, but anyone who wants to try can probably figure it out. You can see how to remove the motherboard of the iPod here to replace the 30-pin.
Before you even try this, use another cable. 30 pin cables are very flimsy. They break all the time. If it still does it with a different cable, it's the connector on the iPod.
And even if it's just cold solder you'll probably destroy it. You're better off replacing it even if it's just cold solder causing it.