As stated, the core of any melee build is levels in Brute. Everything else is just flavour. The master traits are nice, but it's Brute doing the heavy lifting for your build. This means that virtually any build can be successful in melee (as long as you stay away from shooting traits, duh) and in AoB. It doesn't make it easier to get going, but you do have a huge amount of freedom in your build. Also, read up on gift dropping (it's very useful for melee "door-watching", busted armour is still great to carry for AoB games) and how to make an AP chainsaw (it's your mid-tier weapon of choice between a normal chainsaw and the spear).
On higher difficulty levels, skipping a few enemies at the start isn't a huge problem (unless you're going for specific medals/badges). You get more experience anyway, with more high-level enemies to kill, so it evens out very quickly. It's a matter of making it far enough to get your equipment stacked up nicely, one level of experience won't make nearly as much difference as saving a couple of medikits, armours and some HP.
MVm is awesome. Always has been, always will be. It's not as good at hp-farming now, but it's still very nice.
For a different "masterless-master-build", try Bru-Bru-Bru-Ber-Int-Int on a scout. In any order you like really (with Bru to start with). As always, Int(2) is virtually a master trait on it's own, and melee is also the build that benefits most from knowing where power-ups are. Sometimes you can plan entire levels on "globe-running", especially if they're interspersed with zerks and invulnerabilities. It also helps you learn a bit more about the AI, so eventually movement patterns of enemies become more instinctual to you.
Use run. A lot. In fact, that's why I like melee builds so much. They teach you how to press the run button at the right time. I often forget in normal runs (even in shotgun builds) and still succeed. In melee games you can't forget or you die. Every small medipack, every small life globe, is an opportunity to run more. Often the extra health is simply a nice bonus side effect. Plan when to run, but just make sure you do it often. Bru(3) is a massive to-hit bonus, so don't worry about accuracy losses.
That's about it for my advice on melee games. For normal games, it's easier. Go for a MAD build (it gives you a good weapon and is pretty survivable). Remember that SM turns RLs and MLs into awesome weapons as well, so it's useful for any build. Or try a scout with Int(2) straight up and build into rapid-fire afterwards, or try a MFa or Msh build. All these builds let you learn and have a nice "levelling-effect" curve, where you get more powerful right when you need to. You'll have Rel(2) just before the arena, with SM often coming in during the fight, or you'll have Int(2) just before it. Both of these traits are ridiculously useful at that point, so you'll save heaps of ammo, life , medikits and random junk and put yourself on a good footing for later levels. The rest of the game gets a heap easier from that point onwards (remember to rocket-jump once towards the arena master in the chained court, bye-bye barons).
I could give TONS of advice for normal games, but they're the "easy" starts, even on UV.
