Ah, good to know that it can be done with a -real- strategy.
Here's how I do it:
Let 6 guys show up, use special Buy egg automatic Buy club men and use special when able Keep buying club men. Lots and lots and lots of club men. Continue to buy all 4 egg automatics while remaining in the first age and buying lots and lots and lots of club men. Shortly after the enemy reaches the modern military age, upgrade to the same and buy as many double cannons as you can. These double cannons and your special should be able to kill everything until you upgrade to the final age (before the enemy) and get the $100k turrets. Buy 4 of the best turret, then wait until you've got enough money for a tank followed by 3 or 4 super soldiers. Win.
Why it works: In most cases, the enemy can only kill 1 clubman per attack, so their kill rate is limited by their attack speed. Club men become trivially inexpensive past the 1st or 2nd age, so you can build so many that the enemy just can't get through them. Also, when the club men get backed up enough, they all start stacking in one spot. When an enemy gets through to the big stacked spot, he can get attacked by 20 clubmen at once and die quickly.
Micro-management details: - Keep the fight in range of your egg turrets. If your clubmen go forward, they become basically useless. - Keep an eye out for dangerous situations. 3 or 4 riflemen or ranged soldiers can tear through your clubmen far faster than the melee units can. Prepare a huge buildup of clubmen as soon as you see a situation like this, and possibly save your specials for these occasions.
The guide that zarakon posted for impossible doesn't really seem to work. I did try that for harder and it did work. It's a good strategy for harder, but not for impossible. All, you need to do in harder is when the people that shoot come always put a caveman out, or they'll shoot your base and you'll be defeated.
I have tried the Zarakon tactic twice now and it DOES work.
The trick is to get the special to kill a few of their clubmen early on, then buy an egg canon immediately. Wait until their clubmen are getting hit by the egg canon then quicky make as many club men as you can. Keep making the club men. Eventually you will start to make a profit as you will be able to use a special before they can attack your base. You will also find that you can't physically spend the money you are earning fast enough.
As you gradually build up numbers of clubmen you will find that they are actually standing next to each other, thus hitting the enemy even harder. Resist the urge to buy the sling shot people or the dino riders. When you have saved up enough buy another turret and another egg canon... Keep doing this until you have four of them.
I have found that when the enemy comes at you with an army dude carrying the gun - this is a good time to start evolving. Make you sure you have about $20,000 before you do this though. Also if you time it so that your special can be used immediately this is a good tactic. Evolve to the stage with the aeroplane and the bombs, and use the special. Upgrade one of your turrets to the best, and buy a few of the basic soldiers. If you can't afford the best one go for the second best, and upgrade the turrets as quickly as possible...eventually having 4 of the best ones. This will hold off the enemy for a while without needing to buy and foot soldiers. When the God's Blade dudes start coming, or if you have $40000 in the bank evolve again and buy an ion canon. Keep upgrading these to the best one. When you have all four with the blue ion canon they will not be able to penetrate your base ever. You can then just leave your computer for a while... maybe get a nice cup of tea, then come back and buy 3 - or as many as you want of the super soldiers and watch them win.
I'm pretty good at the game, but can't give any advice other than yours on Impossible, I can barely get halfway through it. I'll see if your strategy works out though, thanks.