They should rework the gods and let non clerics and non paladins choose the gods they want. It makes no sense for a good cleric to choose an evil god like Shar or Bhaal. You should be choosing good gods that go with what you want.
You can justify any combination through roleplay. What you can't do is roleplay as a chosen of a deity the game does not support.
