Being most of the way through my second, mele/punching/pistol play, I agree with most of what Vorph said. You need not actually buy any ranks of stealth (AG9 and a couple magazines and/or chameleon pieces do enough), but you damn well better have blitz and be using basic stealth to close in. Pure mele will never work, because some fights demand ranged solutions (Suiciders, high mounted turrets, Mirelurk Queens), so minoring in pistols or explosives is essential. While I have not been able to obtain the Instigating weapons to experiment with, I do have most of the other key ones out there. For reference, I have Mele 4, Unarmed 4, Bloody Mess 3, Blitz 2, and most of the crafting perks.
Pickmans- Easy to obtain early and a solid weapon, until you get around 20-30 and can attempt getting something better. Its fast and, if you do the ping pong blitz thing, fairly powerful for the early levels. It does most of its work by the Bleed damage, so for harder fights, you may need to pick away at an enemy and then run for cover.
Super Sledge- Buyable early and good if you are not doing the VATS thing. Comes into its own a little when you get the AE mele perk, but still too slow to be useful after a certain point. Great companion weapon, though.
Kremvh's Tooth- Get this thing the moment you can. Right out of the box it is on par with the best weapons in the game. I have not found another legendary machete to place the mod on, but its not hard to figure out that the moment you do this weapon instantly becomes the best mele weapon in the game. It also has the added bonus of being the fastest mele weapon you can use in powered armor (outside of fisticuffs).
Named Bat from Diamond City Vendor- Modded up, this is probably one of the better weapons I have used. It does damage on par with most two handed weapons, but with the 40% VATS cost reduction you can actual get more swings off with a full bar than when using Pickmans. Around the time you are perked up for mele (say, 25-35), this is the best weapon out there that does not require a luck based legendary drop to happen. I was genuinely shocked at how good this weapon turned out to be.
2076 World Series Bat- Obtainable from a fairly rough area (for a mele specialist) behind some major locks (Cait can beat them all), you would think his bat would be better than the one you can snag off of the vendor. It is a lot of fun to send dudes flying miles away, but it does not out perform the vendor bat and occasionally bugs VATS if you launch guys. The one cool thing with it is that the proc happens a lot more in real time combat and with high luck, which when combined with AE mele weapon perk can send packs of ghouls into the stands. Fun to play around with, but you will undoubtedly have a better weapon by the time you can get this one.
Named Quest Deathclaw Guantlet- I forget what quest drops it, but there is a named gauntlet you get that refills your AP on a crit, which is needless to say beyond broken if you have a lot of the luck based perks stacked with it, as you can have a never ending chain of VAT and Crits going on. Only issue is it is a tad heavy on its AP cost and sometimes you just can't get the synergy going with it. Its still a pretty good weapon, if Unarmed is your thing.
Named Power Fist quest drop- I think this one drops from the main quest chain, but its a Power Fist that does progressively more damage with each hit on the same target. With a high enough AP pool, you can go toe to toe with nearly any enemy that exists in the game, even on survival, but if you are heavily invested in Luck the Deathclaw Guantlet I mentioned is better. At the point I am at, it is a toss up between this thing modded up or the named bat I bought off of the guy in Diamond City. Both are damn effective, especially with Blitz ping ponging. The basic power fist is not really that good, but this weapon is worth it for the special effect.
Bare Hands- Stack the Jacket from the Atom Cats and any other similar gear at high levels and you will see this actually do some serious damage, though not enough against seriously armored guys. Unfortunately, you need a high luck and to Unarmed 5 to get the full power out of this, but if you do go this route the payoff is pretty good. ITs just a rough path getting there. When power armor cheesing, the mele reflect mod (or Tesla) combined with all the arm upgrades makes this the easiest and cheesiest combat in the whole game (and that's saying something) because of how cheap punch attacks are in VATS. The major upside is that the VATS animations are awesome and spammed fists will (at mid levels of unarmed) nearly always disarm your opponent, which can trivialize several difficult fights (Kellogg for one) in the mid game. You pretty much have to suck down the chems like water on survival, outside of power armor, to be doing this though.
On mele in general, I don't think there is any magical requirements to pull it off and make it workable except for one. Blitz (and by extension AGI 9) is a must have perk. Do not even bother trying to mele without it. Further, once you get the second rank at 29, you can do intentional ping pongs in vats (targeting to separated enemies alternating them) to cash in on the charge damage bonus, which is often more than the base damage of the weapon you may be using. The side benefit of taking Blitz is that you won't really need to invest in the sneak perk, as your base AGI will give you enough to close into blitz range most of the time. Another good tip is to throw grenades into groups before engaging, if stealth is not an option. The stagger effect from the explosion will give you some time to apply VATS beatdown without getting retaliated against as much. Finally, there are times when real time attacks are superior to VATS, mostly once you have the AE mele weapon perk. Standing firm in a hallway chokepoint and swinging at multiple ferals as they come at you in groups will occasionally yield better results than spamming VATS, which can put you out of position a lot.