Yes, that would fit. The mother of all giant spiders, Ungoliant, was originally a servant of Melkor, but turned against him. Some should serve the Shadow, some should be wild.
I'd say that Ungoliant was for a time an
ally of Melkor,
not a servant. Melkor himself was rather afraid of her. Ungoliant was actually a rather powerful Maia who fell on her own (she rebelled just like Melkor did, but was never one of his followers. She was arguably more evil than either dark lord), capable of consuming light and "emitting darkness so deep it was a substance of its own, not merely the absence of light" (I forget the exact wording), but there were other giant spiders that were merely animals. She mated with one, and created a race of spiders (ending with Shelob) that was partially supernatural.
I don't see Giant spiders as buildable units. Having one barbarian (or possibly shadow) hero with the ability to spawn more would be better.
Honestly, I have trouble seeing how Tom Bombadil can fit in the game as a unit; I would rather he be limited to a series of events, which won't necessarily have much impact on the game.
I'm undecided out how how to implement the Ents (their own civ, barbs, spwned by events, etc)
It wouldn't be particularly hard to have a unit spawn randomly, but there could be trouble with making a Watcher be able to move in water and rivers. I guess you could make it able to move on "all tiles" and then restrict its movement to those next to rivers (probably requiring SDK changes). Of course, you could also try changing rivers to be water tiles instead of a feature between tiles (possibly a good idea seeing as how many were navigable and hard to cross), but that would be a pretty major change from the way Civ IV works now (I guess you could handle most of it by using custom maps with long tin sections of coasts).