The only way to remove the randomness from the second is to make it so that it doesn’t attack paladins at all. Which is fine by me, but just saying.
I don’t think you could remove the randomness from the first one without creating more information for the Shaman. If it goes down the list in order, the moment it skips a name you know that’s the Deathcaller. If it goes by a specific class order, then you will be able to figure out who each player is, and you will know who isn’t what they say they are when you get to a place on the list and you don’t get their name. If it goes by any order, you will know that when it skips a name, that’s the Deathcaller.
Not all randomness is bad. After all, most N1 targets are chosen randomly.