Visually checking your battery connections isn't good enough, they can look fine and still be the cause of your problem which is usually nothing more than a bad battery connection You really need to physically remove both connections and use a wire brush on the posts and connector interiors, then securely reinstall and tighten them down.
If you can't get the connector tight afterwards, it's because it is worn inside. You can fix that by removing the bolt and using a Dremel cutting wheel to cut away lead on both sides of the gap so it can close tighter against the battery post.
If after doing this you still have a clicking starter, odds are the battery is dead or bad so take it to a battery shop and get it load tested which will indicate its health. Rarely is your problem caused by a bad starter.