If you don't want to use Versatility then you could use a dexterity based build that uses either pistols, SMGs, energy pistols, or blob pistols because they're all light weapons. Your melee weapon would also be a light weapons, so unarmed, fists, or knives. So yeah, the taste of blood idea seems solid. I'm certain it's possible to beat dominating with a build like this, but I personally don't think I'd find it that interesting because it wouldn't play much different from a Versatility build.
You could also use a minigun build. Heavy guns scale with perception but require strength. It'd probably be fine to put some points into melee, especially if it's a melee weapon that'd compensate for the minigun's shortcomings. I haven't played with heavy guns enough to know for sure which melee weapon would be good, but the sledgehammer seems like a decent bet.
Also, I wouldn't say that underrail punishes you for using more than one weapon, it punishes you for not choosing a primary weapon. Ignoring throwables and traps, grenade launchers and blob pistols don't take much investment to be situationally useful. If you have skill points in guns and have strength, grab a grenade launcher for extra AoE and the stun from Concussive Grenades. If you have dexterity instead then you can grab a blob pistol and you suddenly have access to acid damage and a root, a DoT heat damage gun, or a weapon that can slow and freeze targets.
I've actually played a few swords builds that rely on versatility for the grenade launcher, and I'm testing a sword + energy pistol build right now. Energy pistols do require quite a bit of investment to be good, so I'm not sure how it'll go.