This comp is very dependent on basic attacks, Heros like LiLi and Cassia counter this comp hard due to blinds. But this comp also pumps out a lot of damage while having very good lane clear. The comp also has a lot of cc and a lot of AoE. It is overall very flexible.

Rexxar can be swapped with thrall, they both have their weaknesses and strengths. They both fit in the comp very well. At worst Samuro can be swapped for thrall if the enemy team is heavy on blinds.

Gul'dan is the main back line in this comp. Rexxar is back line but does a lot of his damage in the front line. Gul'dan also has a lot of sustain on his own and can pump a lot of damage as well as being flexible for the team applying dots, straight damage, and some CC. He also is going to be a primary target in the comp next to Rehgar.
BUILD
This build applies a lot of instant damage. The level 13 talent can be swapped from "Dark Bargain" to "Fel Armor". Fel Armor is a very safe route all around while Bargain is a little more of a risk with the respawn timer being increased.
With that his level 10 Ability can we swapped to RoD if CC is not an issue from rexxar and reghar.
WEAKNESS
Mana and health pool, Gap close.

Garrosh is the tank in the comp. He applies a lot of pressure and is high sustain. He can also make a lot of plays for the team and is a very valuable pick over all.
BUILD
Garrosh's level 13 talent can be swapped from "double up" to "Bloodcraze". Double is going to give a little more sustain with armor but if your are going against a comp that has anything that decreases armor bloodcraze is the way to go.
WEAKNESS
CC, Armour Break, slow.

Rexxar is a very flexible hero in this comp, he can be played in many different way including a misha build, a rexxar auto attack build, and a lane build. He applies a lot of damage front line and back line as well as putting out a lot of CC with misha. Rexxar can be swapped for thrall. Rexxar should be swapped to thrall in a sisutaion where the enemy team has some sort of blind.
BUILD
Rexxar's first talent tier is extremely flexable. "bird of prey" is all around good in laneing and team fighting for clearing minions. "easy prey" is better for a main lane build for rexxar. "Flair" should be chosen if there are any stealth heros on the enemy team. You can keep flair up 100% of the time.
Rexxar's level 4 talents can be swapper from "Grizzled Fortitude" to "Animal Husbandry". If rexxar is having a hard time staying alive, grizzled is the way to go. But if Rexxar is having an easy time staying alive animal husbandry is the way to go. The goal with this talent is to play as safe as possible to stay alive. if chosen this late game rexxar will dominate with his massive amount of health. Something to note is that if misha dies you do not lose stacks.
Rexxar's level 20 tier can be swapped from "Frenzy of Kalimdor" to "spirit bond". Frenzy is all around good pumping a lot more damage and slowing enemies, but spirit can be very good if the Rexxar player is very good at controlling misha. If they are still new or not as good at controlling misha frenzy is the route to take.
WEAKNESS
Armor breaking, CC, misha control, slow.

Rehgar is the healer in this comp and make it extremely valuable. He applies a great amount of group healing and cant make plays and team fights easy with Bloodlust epically because there are a lot of auto attacks in this comp.
BUILD
The level 10 abilities can be swapped form "Bloodlust" to "Ancestral Heal". If the enemy team has a lot of blinds and group heals ancestral is the way to go.
The level 20 tier can be swapped from "storm sheild" to any of the level 10 tier upgrades depending on the ability chosen. Storm sheild is a solid route to go regardless. Storm shield combos very well with lust but Gladiators war shout is a very good way to go. But Farseers Blessing is not as good. If you go heal Storm sehild is going to be better.
(This is the lightning sheild build, The heal build works as well)
WEAKNESS
CC, and mana burining.

Samuro is the main frontline damage in this build. He is very good overall, he is very versatile and can be hard to shut down. He combos very well with bloodlust as well. He can apply a lot of pressure to a team with his images. In worst case he can be swapped for thrall as well.
BUILD
The level 20 talent can be swapped from "dance of death" to "Blade masters pursuit". Dance is good all around but BMP is very good with lust and good when the player is good at diving and controlling images to put out auto attack damage.
(This is an auto attack build, you can play Samuro in all different build including Image build, and Crit strike build, as well as all sort of flex build with combos of all of these, the build should be based heavy on what the player is best as doing, incluiding diving, mirror control, and front line damage, as well as everything in between.)
WEAKNESS
Blinds, high area damage, and CC.