While I don't claim to know much Tanya (and indeed, the only reason I know what you're referring to is because it's in the first chapter, which is about as far as I got), the way I understood that exchange was if someone viewed themselves as a Rasha, then other issues could arise from that (i.e. depression), but not that a person couldn't do Teshuva. It would just be more difficult, as his mindset would be working against him.
And before I get to the main part of my answer, I'll head off comments by saying, no, I do not know where the sources for these statements are off the top of my head, so if anyone else does, I will gladly edit them in:
To the best of my knowledge, the Gemara and Midrashim are filled with cases of people who did Teshuva after living what some would consider the worst of lives. Even one of the greatest Amoraim, Reish Lakish, originally was a reformed bandit.
I believe there is only one case in the Gemara where someone was told (via a Bas Kol - Heavenly Voice) that 'everyone could do Teshuva except for Acher'. Even in that case, it seemed like the Tanaim themselves might have disagreed with the Bas Kol, as Rabbi Meir (a student of Acher) implied that Acher could still do Teshuva. (One explanation for the Bas Kol that I remember hearing, again I don't remember the source, is not that Acher couldn't do Teshuva, just that he wouldn't be given Siyata DiShemaya - Divine Assistance)
As to your comment in the beginning of your question about not being forgiven for the 3 cardinal sins, do you have a source for that? As Yishai also commented, I don't believe they are unforgivable. While one might still be obligated in a punishment on this Earth, which might in itself be the Teshuva, G-D has His own 'accounting', where a person could be forgiven.