How to avoid the situation in which player 2 knows for sure that player 1 chose the King?
Remove the appropriate number of random characters face-up, if a King is revealed reshuffle. Then randomly select a character card and place it face-down

This will still have you reshuffling the character cards 25% of the time in a 4-Player game (if you remove the King from the face-up random cards, you reshuffle 100% of the time), but it is much better than The only two other possibilities that come to mind. In this way, the second player doesn't know if you chose the King or it was removed face-down randomly.


Remove the exception for choosing a new card if the King is revealed face-up
Allow the First Player to choose between the Last Players face-down discarded card, or their original choice


Both of these suggestions have their own issues. If you allow the King to be removed face-up, you are changing the odds that the First Player changes each round. In a 4-Player game, you have tripled the chances from 12.5 to 37.5, that the King is unavailable.

With the latter suggestion, the first player knows all the roles that were chosen. This means that they are certain to hit with the Assassin or Thief. 

BTW, The first player sets aside one character card face-down with-out looking at it, according to the rules (not that this isn't easy to deduce).