Here's a quote from the Hobbit talking about Bilbo's journey home, 'He had many hardships and adventures before he got back. The Wild was still the Wild, and there were many other things in it in those days besides goblins.'. It then explains that Bilbo was safe though because he had Gandalf's with Him and Beorn much of the way.

For a bit of fun, anyone want to imagine what some of the 'many other things' might be' ? Even adding TOR stats and still seeming like Middle-earth?

There are Stone Giants in the Misty Mountains in the Hobbit.

Thorin mentions them throwing rocks. They are not mentioned in LotR. But what were they? Trolls? Actual Giants? Lesser Maiar?

Actual Giants I think. Gandalf mentions them as well when he talks about trying to find a friendly one to block the entrance to Goblin Town.

Well you've got bears, mountain lions, giants as mentioned, in bits of woods that are intact from the elder days more trees like huorns/old man willow, snakes, and bandits or raiders from the east (that makes more sense in eastern wild).

Per rules trolls, bats, spiders, wolves (not all of whom are bad, you could have a noble wolf pack leader contending with an evil warg trying to take control).

I think it's okay to, judiciously, have "fell beasts" of various sorts. Creatures left over from Morgoth's meddling. The Watcher in the Water is presumably one such. They should have a unique terror feeling to them so can't be "every week" villains.

To keep the stock goblins etc. fresh I would make sure to personalize them even more than the rules do. Mention clans/tribes/gangs and their particular iconography, big boss, tactics, grudges and connections (ah this is the group that killed your father) etc. One bunch is big on wolf riding archers, another big on poison etc.

You can have the odd dwarf or other who has fallen to Shadow and Dragon Sickness or other such issues (shades of Mim the Petty Dwarf).

You can have a regional "presence" like Caradhras, the "other evils older than Sauron".

Perhaps madmen who have escaped Shadows torment (former prisoners of orcs and goblins, or prisoners of Dol Guldur who were ignored and left behind when its power fled 5 years ago) - they may have useful information, clues to help on adventures etc. There is always the risk, going back to Silmarillion, that such tragic figures have been "broken" and are now agents of Shadow.

As a different problem, heroes might face illness - small echoes of the Great Plague afflicting a village - with quests to find cures or sources of it.

Not explicitly, but if you read the description of the Fellowship trying to get through the Redhorn Pass with a suspicious mind, it's entirely possible that what Tolkien has in mind is giants above them throwing rocks, even though the storm keeps them hidden.

Etten from Ettenmoors is an Old English derivative of Jotun. It is likely that giants live,or did live, in Eriador. I could also see Ettins referring to the two headed species of Troll (from DnD) without too much difficulty.
Any sort of old English, Gemanic, Celtic or Scandinavian creature could fit in no problem. Swanmays, Barghuests (fell spirits in the form of black hounds), Draugr, Black Annis Hags etc could all be given a Tolkien spin.
The women in the Black Tarn are a Tolkien variant of Naiads. Why not Dryads in Mirkwood as capricious nature spirits. Oreads also in the mountains and hills of Wilderland. Time to get out the old monster manuals methinks.

Halbarad good stuff.

I've been wanting to find where I put my old dictionary of faery lore (not the glossy coffee table book sort, an actual dictionary of english stories about creepy fairies, black hounds, hags etc more often than anything cute hanging out in garden).

Didn't Aragorn refer to the Ettinmoors as 'troll country' in answer to Sam question (whether the paths at the foot of weathertop were made by trolls, and if this was troll country), or did he mentioned to Troll Shaws?

Personally, I'd say that 'giants' are in fact trolls, probably from a different breed than the stone trolls that turn into stone when exposed to sunlight (mountain trolls perhaps?)

Tolkien have been known to give different names to the same species (orcs vs goblins), especially if the Mountain Trolls are smarter, taller (or less hunched) and stronger than the slow-witted, sunlight-aflicted trolls that people know from their folklore (and don't have a proper name for these 'giants').

Glorfindel

You could be right Glorfindel. The thing to consider is whether we regard all Trolls as being servants of the shadow( like Orcs and goblins)? Gandalf suggests that there are friendlier giants that might be employed to block the back gate to Goblin Town.

What about a Lindoorm or Stoorworm? These might certainly be Fell creatures that Sauron's minions have released from the cavernous depths beneath the mountains.

Irish Vampires (Dearg Dul) would certainly be another good fit for an alternative version of Tolkien Vampires. Check out the tale of Abhartach for a possible idea for a vampire spirit in a Dwarf body......

A variation on the Kelpie would work well too. Appearing either as an impossibly beautiful woman or a magnificent steed, it would lure men to the deaths by dragging them into lochs and drowning them. It was occasionally known as a Water Horse.

...and speaking of worms, what about cold drakes? Are there any of those left in Middle Earth?

Were there any other creatures designed for playtests that didn't make the final printing?

Interesting thoughts here, thanks all. I do want to spring a few surprises on the players so it's great to have a few ideas like these.

Lets not forget ruffians of all sorts. There's a gate at the entrance of Bree and of Buckland for a reason...

The Mirkwood forest has its spiders, but other insects could have suffered (or benefited?) from the shadows of Agmar: centipedes and caterpillars of monstrous size.

Also, the nazguls were given mounts "from another age". Other dinosaur/dire type creature could exist in the north, recently 'thawed' by some magic or awaken by sauron's call.

Interestingly enough, the usual medieval menagerie of gryphon / basilisk / manticore / chimera etc (Greek origins?) seems absent from Tolkien work. I'd be tempted to research the northern mythology for other mythical monsters and creatures. A few of them seem to relate the tale of gigantic cows or cattle of some sort. Actually, isn't there a large ox-type creature in the plains of Rhovanion (from which Boromir's horn is made)?

I think you are thinking of aurochs.

The Bestiary monsters are mainly from Greek via Latin tradition.

In terms of direct Northern European legends - there are a few types unused in Tolkien that may or may not fit. Human-like trolls, merfolk, giants, valkyries, huldar, all come to mind.