Since there are no guides for Lord Victor Nefarius on Heroic yet, I thought I would present mine. I defeated him on the first try with this deck. It's nothing incredibly special. You might recognize it as the current meta "control paladin", with slight modifications to accommodate for PVE.
What is necessary?
Equality: This card is just too valuable to leave out of the deck, especially since it allows your Silver Hand Recruit to kill a high attack minion with little effort. This with Consecration is an easy way to wipe Nefarian's side clean. A Wild Pyromancer can be quite effective as well. You should mulligan for an Equality!
Wild Pyromancer is a great card to have with Equality, as it allows for a Turn-4 board wipe. If used in conjunction with Consecration, it's a 3 damage AoE. I highly suggest you mulligan for Wild Pyromancer. It is an easy way to destroy Nefarian's board.
Muster for Battle: This card is extremely powerful alongside Quartermaster. Nefarian will rarely clear the board of Silver Hand Recruit unless he has a Consecration or Flamestrike of his own. If used with Equality, you might pick off some easy targets. It allows for early presence and a quick way to kill Nefarian's Turn 2 minions.
Something I have noticed is that the AI likes to target "threat cards" over going face. These cards are pretty typical, as even human players would target these in many cases. Knife Juggler, Sylvanas Windrunner, Emperor Thaurissan and Cult Master are a few examples. These cards are by no means necessary to the deck, but you may notice they will buy you a turn or two.
Doomsayer: (Replaced Mind Control Tech) Reports from comments suggest that Nefarian rarely has 4 minions on the board, making MCT a waste of a card slot. Instead, I opted for another way to clear the board. It was just too difficult to rely on Equality and Wild Pyromancer to do the job.
Big Game Hunter is an easy way to deal with high attack minions! You may even want to consider adding a second one. **EDIT: Added a second Big Game Hunter for MCT. If you don't have it, I suggest adding another Antique Healbot.
Antique Healbot is excellent for survival. Once again, you may want to add a second one to increase your chances!
Aldor Peacekeeper against high attack minions is very useful, especially in the early game. Don't be afraid to use them. Nefarian's minions typically range from 5-8 damage I believe, and they hit like trucks. Combo with a Sludge Belcher to block damage.
Lay on Hands for healing purposes as well as card draw.
Ironbeak Owl is somewhat strange for this fight. However, I found it useful against Twilight Drake and the Blackwing Technician. Feel free to replace this card if it is not living up to your expectations. (maybe for an extra Antique Healbot or Big Game Hunter?)
Piloted Shredder is useful when Nefarian uses an AoE spell to clear your board. It allows you to have a minion ready on your next turn.
Zombie Chow is a good 1-drop, a "threat card" and a good way to remove some of Nefarian's armour stacks. You don't really have to worry about the heal as it will most likely be dead by the time you remove all of the armour. EDIT: I opted for a second Mind Control Tech as I think it will allow for better chances to take control of Nefarian's minions. He is also apt to killing his own minions once they are taken.
Sylvanas Windrunner. I think this card is quite useful as it is an easy way to clear a minion AND take control of another one. A good replacement would be Loatheb. It costs 1 less, has the same stats and slows down Nefarian in terms of spell use. It could buy you an extra turn. As mentioned in the comments, I even considered Alexstrasza for possible heal or an easy way to lower Nefarian's health.
Tirion Fordring. I believe it is difficult to replace because of the Taunt + Divine Shield, as well as Ashbringer, but I think Coghammer would be an interesting pick. Sure, it removes a minion, but it gives a random minion Taunt AND Divine Shield, and provides a weapon. You may want another Taunt minion altogether, in which case I would probably grab a Sunwalker.
Emperor Thaurissan. The more I look at it, the more I think it is unnecessary. I would trade it for Kel'Thuzad. Edit: Made the switch. I think Kel'Thuzad is a much better candidate, if you combo with Tirion Fordring, Sylvanas Windrunner and Sludge Belcher.
You will notice that as soon as you have board control, this fight
is incredibly easy gets easier. I think the trick is to fill your board with Silver Hand Recruit and to Quartermaster. Do not overextend and play defensively. It is much easier to deal with a single minion than seven.
Here is an example video of my playthrough against Lord Victor Nefarius:
Check out my other decks for the League of Explorers bosses: