Personally, I would do this “simple but major” change: Poisonous on Murlocs only work once per battle (and if it’s blocked by Divine Shield, it’s still gone for the rest of the round, but it will be back up in the next one).
This would be a significant change because it would open up some additional counter-plays.
For Demons, minions like Void Lord would become important because additional bodies can soap up a poisonous hit.
For Mechs, we all have our “favorite” Mech that spawns more taunt whenever damaged, and we will have a variety of other mechs that can spawn more minions on death, potentially blocking some poison.
For Beasts, tokens could end up baiting all those poisonous hits away from your Scavengers.
Ultimately, this change would allow other minions to have a potential defense against all those Poisonous Murlocs. Positioning will be even more important. For Murloc Players, they will need to boost their Murloc’s attacks a bit more with the help of their new Murloc Legendary.