I had a lot of free time and decided to waste it like this. I tried to ignore wow era alliance/horde locations. Forgot Crestfall, little isle east of Kul Tiras. Also, locations might be a little off. Keep in mind that some of those settlements are pretty small and irrevelant but have good location and have no good alternative.
1) Dunemaul Compound
-Village or motte and bailey
-Garrisoned by ogres
2) Lost Rigger Cove
-Town
-Garrisoned by pirates
1) Gorishi Hive : It might appeared after the starting date but there is no other viable settlement in Un'goro crater.
-Village
-Garrisoned by silithid
2) Southwind
-Village or town depending on strategical need
-Garrisoned by either silithid or night elves depending on if you consider War of the shifting sands a past or future event.
3) Hive'Zora
-Motte and bailey
-Garrisoned by silithid
4) Hive'Regal
-Town
-Garrisoned by silithid
**Second Cenarion hold at north is Valor's Rest
1) Bramblescar
-Village
-Garrisoned by quilboars
2) Lushwater Oasis
-Village
-Garrisoned by centaurs
3) Blackthorn Ridge
-Motte and bailey
-Garrisoned by quilboars
1) Thal'darah Grove
-Motte and bailey
-Garrison by night elf druids and taurens
2) Stardust Spire
-Village
-Garrison by night elves? Or furbolgs
3) Dry Hill??: Thats just a harpy area with some tree nests, added because area was empty, might be unnecessary
-Village
-Garrisoned by harpies
**Thal'darah Grove and Stardust Spire can belong to Night elf faction I guess? But this would probably unnecessarily boost their power.
1) Darkcloud Pinnacle
-Town
-Garrisoned by tauren
1) Satrynaar
-Town
-Garrisoned by satrys
2) Temple of Arkkoran
-Motte and bailey
-Garrisoned by murlocs(and may be sea giants)
**Talrendis point was too close to Satrynaar thats why I didnt included it.
**Mazthoril is a possible settlement south west of Everlook. I forgot it.
1) Mo'grosh Stronghold
-Motte and bailey
-Garrisoned by ogres
2) Dustbelch Grotto: Location is wrong, it was actually at the southwestern corner, but it was close to Uldaman on map, and eastern was side was completely empty.
-Motte and bailey
-Garrisoned by ogres.
1) Mosh'Ogg Ogre Mound
-Motte and bailey
-Garrisoned by ogres
2) Thats the real location of Zul'Mamwe
3) Aboraz
-Village
-Garrisoned by jungle trolls
4) Mizjah
-Village
-Garrisoned by ogres