Hearthpwn

You're probably a very good player since you don't know how to run this deck, gl in rank 25.

I think this deck would be better if you just lose the whole Prince Kelseth part. In this deck Keleseth is used as a win more card that I think has more downsides then upsides. Sacrificing the 2 lost in a deck that needs to curve out while being able to take and apply pressure is an important part of midragne that dies with Prince Kelseth in the deck.  Playing two 1 drops on turn 2 means your a card behind your opponent and this deck is bad at drawing cards and creating value.  And if you're saving Keleseth as a combo piece holding a card as a deck that's trying to curve out can be lethal.I feel like this deck would be better if you made it more Midrange oriented. Instead of Keleseth put in Deathstalker Rexxar. This adds more value and will help with the weak power of 1 drops in the later stages of the game. This also helps the deck consistency in the late game. Because this deck is more of a slow midrange it suffers weak openers and lack of card draw. Adding a card like Deathstalker and 2 drops into the mix will make this a midrange with a higher win-rate against control  and aggro. 

I think the idea is to play Prince Keleseth after Queen Carnassa. I don't think you'd keep him in your mulligan. But you're right about the huge card disadvantage on turn 2, which is why I'd consider adding another Cult Master, Unleash the Hounds and Hunter's Mark in place of the pirate package.

I do like the idea of Deathstalker Rexxar. Infinite value might be the only thing that can keep this deck alive.

Actually you don't want to play a 2 drop in this deck, you want to play two 1 drops (at turn 2) and then on turn 3 play something a little better (Dr. 3 or Companion), the lost of tempo playing the quest is pretty brutal, so I would rather to be more tempoish (while completing the mission) by playing two 1 drops on turn 2, for example, Alleycat and Fire Fly, also there aren't many 2 drops that sinergise well with this deck other than Crackling Razormaw and sometimes Scavenging Hyena, so Keleseth finds his way on the deck for this reason.

J4ckieChan made a Secret Quest Hunter wich uses secrets as 2 drops and the sinergy with Cloaked Huntress as another win conditional, if you want to see a deck with more 2 drops I recomend it.

The idea of making a more midranged style of quest hunter seems pretty nice, Deathstalker Rexxar can help the deck a lot, the problem is: It'll be a lot harder to complete the quest, but how much worse will it be?

As I said in another comment, the pirates are there for weapon removal, you lose a lot of tempo playing the quest at turn 1 (against aggro), so the weapon removal helps recovering a bit. But removing them to add more draw and more tech cards is also pretty good.

Inspired by you hint I made a deck, with a little (veeeery little) guide, take a look if you want: http://www.hearthpwn.com/decks/861885-deathstalker-quest-hunter

What about losing an unleash the hounds and a hunters mark and putting in two tracking. It's a 1-cost card that can get you the card you need (a one drop, your rhinos, or your wardens). Those two cards seem like they could be dead cards in your hand a lot of the time (since you are likely holding them for the right moment).

Seems preety good, I put the Hunter's Mark because this deck lacks dealing with big taunt, the Unleash the Hounds for the more aggro matchups, but if you like, you can take of one Unleash and one Mark, but I do not recomend removing both of then tho, or both of one of them.

It's hard to balance having enough card draw and enough 1 drops, I don't think it needs exactly 10 card draws, but if you want more card draw you can remove a card that's not a 1 drop and put another Cult Master. Then you'll have Patches (Most of the time), Tol'vir, and Master as card draw.

Patches won't count toward the quest, you know.

I know that, but weapon removal helps the quest hunter surviving, I decided to use Bloodsail Corsair because it's a 1 cost minion, also, the patches count as a draw, turning the deck into a 29 cards deck, at least most of the time.