1. "Fully charged battery" - How are you measuring this? Volts or AMPS? Volts don't start your engine, AMPS do. Voltage wise, 12.6 volts is fully charged. You can see 12+ volts measuring a battery, but it if drop to 8 volts when you hit the key, the battery is bad.
2. Dirty/corroded battery connections can cause this problem. Sometimes they may look clean but may not be clean enough. Best to remove the cables from the battery and clean the terminals and the battery posts with a battery brush. Do not put grease on the battery posts before installing the terminals. Grease on top is ok.
3. Are your battery cables lumpy? If they are they are corroded under the insulation and should be replaced.
4. A solenoid that clicks loudly is most likely good. You can verify this with a VOM on the starter side of the solenoid when the key I turned to start.
5. Check and clean the connections at the starter. There's also a wire that goes from the starter mounted solenoid to the starter. This short piece of cable is exposed to the elements and often corrodes and rots away, then power is not transferred to the starter motor. Pretty common especially on old starters on rust belt vehicles.
6. If the brushes in the starter motor are worn out, sometimes smacking the starter motor with a hammer will get you going, but the starter needs to be replaced/rebuilt.
7. If there's any doubt regarding the starter motor, remove it, take it to the auto parts store and have it tested. While you're at it have your battery load-tested.
Don't throw money at a problem w/out doing proper diagnosis.