I have finally been able to put something together that may hold the water!
Unfortunately, i disenchanted the quest, but i'll be hitting rank 5 soon and collecting enough dust to start checking it out in below rank 5 conditiond. Until now, it has been simulated from ranks between 10 and seven and it works great!
Anyway, i found the use of Roll the Bones. The first version was to fill your deck with Deathrattle minions, control the board by flooding with cheap minions until you find Gang Up, copy the minion of your choice, then keep flooding until you hit 5 same minions on board.
Version 1
First i tried using 2 copies of Gang Up to put multiple copies of one minion in the deck so i can pull them out and fulfill the quest. Unfortunately, it proved unreliable since it regularly happened to hit one of the Gang Ups the first card after i cast Roll the Bones. So i tried cutting one Gang Up since Roll the Bones cycles very fast through the deck. But it also proved unreliable. Having two of the Roll the Bones is enough to rain on your parade, so one more show stopper is too much.
Version 2
My deck was weak to decks packing bigger bodies and the concept of using Gang Up was not good. I thought there must be something else i can use. Igneous Elemental was weak and i needed stronger Deathrattle body for late game. Then it came to me. The Bone Baron. It had a good stats for its cost, can be used twice with Valeera the Hollow hero power, and it poses enough of a threat to be removed which puts skeletons to our hand.
I also tried the version with Explosive Sheep, Tentacle of N'Zoth and Unstable Ghoul and though it provides a board clear of 1-8 damage, holding the board with minions proved more efficient. I will be futher testing it, it might be useful for late game before the quest turn.
How to play
Early game
As i mentioned, mulligan is very important, if you don't find any Roll the Bones od Valeera the Hollow, change all cards, it doesn't matter what you hold since all the minions are dirt cheap. You don't have to play your quest immediately since you'll be using it for Skeletons, but play it when you have one mana left and nothing to play to keep your hand as less clogged as possible.
Spam the board and trade as efficiently as possible. Before casting Roll the Bones, make sure your hand is as empty as possible to maximize the draw and have at least one mana left so you can protect yourself from overdraw on the next turn by playing a minion you draw. To secure from overdrawing, have no "draw a card" deathrattle minions on board or make sure you have more mana left fo play the minions you drawn. Make sure you have Valeera the Hollow in your hand before cycling so you don't burn her.
Mid Game
Things are starting to heat up, the opponent (unless it is aggro which you usually crush because of amazing hand fill) should already start to churn out some big minions, taunts or board clears. Be careful what you play, if you think you can end the game by going face, do it, otherwise, trade efficiently and get your taunts up to protect yourself. If you have a Bone Baron in your hand, drop it. You can drop both if your hand is not too full, but four skeletons is usually too many if you haven't played the second Roll the Bones
Late Game
It's magic time. This one can be very tricky. Make sure you play Valeera the Hollow on cleanest possible board and as soon as possible. If you have the coin, use your hero power to put two skeletons on board. If not, don't play it, play another one mana minion if you have any left. On turn 10, you should be able to put 5 skeletons on board if you popped both of your Bone Barons, and activate the Crystal Core. If not, make sure you have Bone Baron in your hand so you can drop them twice with hero power. After that, keep pumping 5/5s.
Card Choices
Undercity Huckster - Good stats, gives you a card that can turn the tides sometimes and doesn't interfere with card draw.
Clockwork Gnome - Good attack, nets you a spare part which can be very useful.
Mistress of Mixtures - You'll be probably taking a lot of damage, while the opponents health is not important in the beginning.
Zealous Initiate - Not particularly good stats, but they transfer to another minion, and your board will be always full so it can't backfire.
Zombie Chow - Like all late game decks, this one includes Zombie Chow too, since healing your opponent is not an issue early game.
Huge Toad - Magnificient card, hard attack and a deathrattle that hits once more.
Loot Hoarder - You'll be emptying your hand VERY fast, so you need a refill. Good attack.
Volatile Elemental - Horrible stats, but 3 damage to a minion when you're trying to enforce board control is a lot.
Dancing Swords - We're on to some mid game minions. 4/4 for 3 mana is excellent. Your opponent will draw a card when it dies, but you shouldn't be too concerned about that, you'll always have card advantage.
Deathlord - We need taunts, of course, and what better than good old buddy. Sometimes it can shitstorm on you, but it's a good taunt.
Eggnapper - 5/3 in stats for 3 mana, nice value, strong attack.
Harvest Golem - 4/4 for 3 mana, good against board clears.
Arfus - Geart card, every choice you get is fantastic.
Other card considerations
Shallow Gravedigger - It has a good attack, and you may get a cool card out of it, but it usually dies without doing anything or leaving anything behind.
Vryghoul - A fine card that needs a bit of a setup, unfortunately, opponent usually ignores it since it's you doing the trade and clearing the board.
Spawn of N'Zoth - Can be a game changer, but to problem is CAN BE, it's too situational for such low stats.
Infested Tauren - Besides taunt, it gives you another 2/2, so it's taunt and 4/5 in stats for 4 mana. 4 mana is kind of expensive in this deck.
Piloted Shredder - Excellent value, but 4 mana is too slow. Might try it out in some other iteration.
I tried this deck out at rank 24 (haven't laddered in wild yet this month) and lost five games in a row without being able to complete the quest before calling it quits. Lost to Demonlock, Ramp Druid, Tempo Rogue, and Control Priest (same guy twice in a row). Felt slow and the lack of good removal was painful. I would say my mulligan's were average at best. Became Valeera in half the games or had in her in hand before I died but never finished the quest.
I've piloting it ok on R7, pirate warrior is easy, i even cracked taunt warrior. May need more token deathrattle cards though, i almost always enter fatigue.
I have finally been able to put something together that may hold the water!
Unfortunately, i disenchanted the quest, but i'll be hitting rank 5 soon and collecting enough dust to start checking it out in below rank 5 conditiond. Until now, it has been simulated from ranks between 10 and seven and it works great!
Anyway, i found the use of Roll the Bones. The first version was to fill your deck with Deathrattle minions, control the board by flooding with cheap minions until you find Gang Up, copy the minion of your choice, then keep flooding until you hit 5 same minions on board.
Version 1
First i tried using 2 copies of Gang Up to put multiple copies of one minion in the deck so i can pull them out and fulfill the quest. Unfortunately, it proved unreliable since it regularly happened to hit one of the Gang Ups the first card after i cast Roll the Bones. So i tried cutting one Gang Up since Roll the Bones cycles very fast through the deck. But it also proved unreliable. Having two of the Roll the Bones is enough to rain on your parade, so one more show stopper is too much.
Version 2
My deck was weak to decks packing bigger bodies and the concept of using Gang Up was not good. I thought there must be something else i can use. Igneous Elemental was weak and i needed stronger Deathrattle body for late game. Then it came to me. The Bone Baron. It had a good stats for its cost, can be used twice with Valeera the Hollow hero power, and it poses enough of a threat to be removed which puts skeletons to our hand.
Mulligan hard for Roll the Bones and Valeera the Hollow (you don't want to mill them).
I also tried the version with Explosive Sheep, Tentacle of N'Zoth and Unstable Ghoul and though it provides a board clear of 1-8 damage, holding the board with minions proved more efficient. I will be futher testing it, it might be useful for late game before the quest turn.
How to play
Early game
As i mentioned, mulligan is very important, if you don't find any Roll the Bones od Valeera the Hollow, change all cards, it doesn't matter what you hold since all the minions are dirt cheap. You don't have to play your quest immediately since you'll be using it for Skeletons, but play it when you have one mana left and nothing to play to keep your hand as less clogged as possible.
Spam the board and trade as efficiently as possible. Before casting Roll the Bones, make sure your hand is as empty as possible to maximize the draw and have at least one mana left so you can protect yourself from overdraw on the next turn by playing a minion you draw. To secure from overdrawing, have no "draw a card" deathrattle minions on board or make sure you have more mana left fo play the minions you drawn. Make sure you have Valeera the Hollow in your hand before cycling so you don't burn her.
Mid Game
Things are starting to heat up, the opponent (unless it is aggro which you usually crush because of amazing hand fill) should already start to churn out some big minions, taunts or board clears. Be careful what you play, if you think you can end the game by going face, do it, otherwise, trade efficiently and get your taunts up to protect yourself. If you have a Bone Baron in your hand, drop it. You can drop both if your hand is not too full, but four skeletons is usually too many if you haven't played the second Roll the Bones
Late Game
It's magic time. This one can be very tricky. Make sure you play Valeera the Hollow on cleanest possible board and as soon as possible. If you have the coin, use your hero power to put two skeletons on board. If not, don't play it, play another one mana minion if you have any left. On turn 10, you should be able to put 5 skeletons on board if you popped both of your Bone Barons, and activate the Crystal Core. If not, make sure you have Bone Baron in your hand so you can drop them twice with hero power. After that, keep pumping 5/5s.
Card Choices
Undercity Huckster - Good stats, gives you a card that can turn the tides sometimes and doesn't interfere with card draw.
Clockwork Gnome - Good attack, nets you a spare part which can be very useful.
Mistress of Mixtures - You'll be probably taking a lot of damage, while the opponents health is not important in the beginning.
Zealous Initiate - Not particularly good stats, but they transfer to another minion, and your board will be always full so it can't backfire.
Zombie Chow - Like all late game decks, this one includes Zombie Chow too, since healing your opponent is not an issue early game.
Huge Toad - Magnificient card, hard attack and a deathrattle that hits once more.
Loot Hoarder - You'll be emptying your hand VERY fast, so you need a refill. Good attack.
Volatile Elemental - Horrible stats, but 3 damage to a minion when you're trying to enforce board control is a lot.
Dancing Swords - We're on to some mid game minions. 4/4 for 3 mana is excellent. Your opponent will draw a card when it dies, but you shouldn't be too concerned about that, you'll always have card advantage.
Deathlord - We need taunts, of course, and what better than good old buddy. Sometimes it can shitstorm on you, but it's a good taunt.
Eggnapper - 5/3 in stats for 3 mana, nice value, strong attack.
Harvest Golem - 4/4 for 3 mana, good against board clears.
Arfus - Geart card, every choice you get is fantastic.
Other card considerations
Shallow Gravedigger - It has a good attack, and you may get a cool card out of it, but it usually dies without doing anything or leaving anything behind.
Vryghoul - A fine card that needs a bit of a setup, unfortunately, opponent usually ignores it since it's you doing the trade and clearing the board.
Spawn of N'Zoth - Can be a game changer, but to problem is CAN BE, it's too situational for such low stats.
Infested Tauren - Besides taunt, it gives you another 2/2, so it's taunt and 4/5 in stats for 4 mana. 4 mana is kind of expensive in this deck.
Piloted Shredder - Excellent value, but 4 mana is too slow. Might try it out in some other iteration.
Polluted Hoarder - Good attack and card draw, but weak body.
Twilight Summoner - Too expensive and situational.
Sludge Belcher - Top of the class, but you should be aggresive, not defensive.
Sorry man, but this deck is a horrible idea, no good to play even against a friend for the giggles.
Waiting to get to R5, then i've got some tweaking to do.
I tried this deck out at rank 24 (haven't laddered in wild yet this month) and lost five games in a row without being able to complete the quest before calling it quits. Lost to Demonlock, Ramp Druid, Tempo Rogue, and Control Priest (same guy twice in a row). Felt slow and the lack of good removal was painful. I would say my mulligan's were average at best. Became Valeera in half the games or had in her in hand before I died but never finished the quest.
I've piloting it ok on R7, pirate warrior is easy, i even cracked taunt warrior. May need more token deathrattle cards though, i almost always enter fatigue.
If you want to try a quest rogue with valeera, I put together one that seems to be working for me:
http://www.hearthpwn.com/decks/912534-hollow-caverns