You are correct that uldyssian was changed couple of patches ago. It will be very tough as melee. Defense also doesn't work well in this fight after changes.
Ideally you'd wanna roll overkill skill and block uberskill for this fight, cratf high phys damage balanced axe. That'd be my pick.
Or some new memes with poison, that single target poison skill could work.
But with least amount of gear changing, use same build that runs overkill+wolf stance.
As for cycles, if you really wanna minmax it? I'd probably stack life and vitality, since we are maxing that out. If you play variant with max strength for damage, then more strength.
Btw, I'm continuing my barb with screaming eagle, bear tank, and I have to say it works significantly better in early ubers already.
Leveling not that much, phys is prolly better, as its comfortable to go through game with life leech.
But at level 110, killing first enemies like Jitan, Akarat, they die way faster than maxed wolf stance + t4 labrys.
Also character is tankier, that -35% enemy damage from screaming eagle adds up, especially against physical enemies that are already weakened by bear stance damage reduction. You can comfortably play with even 200k defense, no need to upgrade gear to max the armors to reach high value, as it is highly advised to do if you play standard build.
Akarat is nice benchmark. Shit gear, not even all T4, amulet 0 skills, akarat dies in literally 1s, instantly blasted. Where with labrys this wasn't that trivial, you needed upgrades and it barely died at that stage, almost outhealing your attack.
You also destroy treewarden guys in jungle right after you enter it first time, about as fast as labrys build at level 125 with all gear and charms from that stage.