Finally legend, after 4 years of casual play on the first month when I tried hard - and it was hard indeed but I succeeded!
After some success with Shudderwoch Shammy, then Odd Rogue, then Control Warlock, and then Cube Hunter, finally - as I become more familiar with the meta - I decided to make the last push with Quest Rogue:
(credits for the original decklist to Sipiwi!)
Here's some sort of mini-guide:
The main difficulty of the deck is to stay alive in the first part of the game. The easiest way to complete the quest is to use Sonya Shadowdancer + any of the charge/rush minions continuosly sacrificing them against one of your opponent's minion (and thus clearing the board too). Otherwise use any cheap mininon you can bounce back-and-forth.
When your quest is completed you should aim to gain board control (against aggro and midrange) and finish your opponent asap (against control).
The ultimate infinite wombo-combo in matches that last really long is playing Giggling Inventor as Valeera the Hollow, bounce it back with Youthful Brewmaster and bounce back the Youthful Brewmaster with its copy from Shadow Reflection. This provides three 4/4 minions (two of them with taunt and divine shield) every turn forever.
My final boss match:
Good luck for your climb, I will gladly answer any of your questions, upvotes are appreciated (thanks in advance)!