Wouldn't this mean that every time a new transaction is added to the block (before its mined), that all nonces previously attempted need to be tried yet again?
Yes, but "need" is a bit too strong of a word in this context. Because you can't predict the outcome of a hash without performing the hash, each new hash attempt is just as likely to meet the target as the previous one. As such, yes, it is possible that a nonce that has already been attempted will now succeed given that the merkle root has changed...but it is no more likely than the nonce you were about to attempt before adding the new transaction. There's no real reason to re-try nonces. The odds aren't any better.
Wouldn't this discourage miners from adding transactions to the block if they have to hash everything with nonces again?
No. Because the odds do not change, there is no negative incentive to adding a new transaction. However, transactions come with miner fees, so the positive incentive is still in place.
Also, is it possible that no nonces could produce a valid successful/winning hash?
Yes, it is possible, although not probable. Remember that a successful hash is one that is less than the target. These means there are quite a large number of nonces that will be successful, however, as a set they represent a very small proportion of the total possible nonces. Even if hypothetically there is a block header that is "unmineable", a competing block would not be. A block will still be found, and it will likely have a very similar set of transactions in it.