Can you tell if that is a very light, barely audible click or a single, rather loud clunk from the starter each time you turn the ignition switch to "crank"? If you see lights dimming significantly when trying to crank the engine, the battery is not able to supply the needed current. Then the problem becomes determining if something is drawing too much current or if a dirty connection or weak battery is failing to allow enough normal current to flow.
Since the starter has been working intermittently, and it's still acting up with a new one installed, I don't think we're looking for something drawing too much current. Start by inspecting all the connections in the two large battery cables. If you have GM's famous side-post terminals, that is hard to do at the battery. Be sure both flat contact discs on the cables are clean and free of corrosion, and be sure those two teeny little bolts are snug. Don't over-tighten them or the threads in the battery will be stripped out.
If you don't find anything obvious up to this point, you'll need an inexpensive digital voltmeter. You'll have to overlook the first part of testing a starter circuit, but measure the voltage right on the two 5/16" bolts on the battery terminals. You should find 12.6 volts if the battery is fully-charged. If you find closer to 12.2 volts, it is okay but it's discharged. Charge it at a slow rate for an hour, then remeasure the voltage.
If you do find 12.6 volts, measure it again while a helper tries to crank the engine. It must stay above 9.6 volts during cranking. If it stays pretty high, as in near 12.3 or 12.4 volts, there's a bad connection further down the line on one of the cables. If you find less than 9.6 volts, it will typically be a lot less. Either the battery is defective or there's still a bad connection on one of the cables where they bolt to the battery.
Saturday, January 11th, 2014 AT 3:06 AM