I've been struggling with the exercises for a very long time and it's
really frustrating. I can easily deal with any type of proofs that I
saw before (e.g. once I saw the proof of a recurrence question I
became pretty good at proving them). My problems start when I face an
unusual question. I feel like I am memorizing the proofs rather than
learn how to prove.
So you do know how to read proofs, but you're finding these ones to be difficult. I think there are probably a few things that are relevant.
One is that differences between ability required by different mathematical textbooks is exponential, not linear. I have seen books titled "Introduction to X" that are much harder than books titled "Advanced Y". Authors have in mind different audiences, and the levels of difficulty are correspondingly different.
Second, it might just be that once you get more familiar with concepts and proofs in a particular area, they will become easier. As some of the other answers indicate, proofs often leave out steps that the author thinks would be obvious for their intended audience. None of us would expect a proof to point out that two plus two equals four. Some things that one reader finds completely mysterious are like $2+2=4$ for other readers. That doesn't mean that the book or article isn't for you, though. If you can work through the missing steps, you will get a deeper understanding of the subject, and after you do that a few times, what was difficult will become easier. (A proof in a book that's a little bit too hard is like an exercise.)
Third, I understand if you don't want to stare at a proof for two hours, but I think that during that period, you may be learning a lot. What you are doing during that time is thinking through different interpretations of the concepts and steps and possible ways to get from one step to another, and thinking about what assumptions the author had in mind. That is a learning process, and I think that doing that helps one understand other things more easily, later.
I do a lot of self-study in subjects that are unfamiliar to me. Sometimes I use two or three books for one subject, because what's left out in one book will be explained more clearly in the other. Sometimes I find that I have to go and read books on other subjects, because the author assumed that their readers would all have a certain background--and I don't have it. That doesn't necessarily mean I read the entire book on the other subject. Sometimes I just read enough so that I can understand the book I really want to understand. This is not a bad practice. I end up learning things that I wasn't interested in learning, but that turn out to be useful later.
(Maybe all of this seems obvious, but hopefully some comment here is helpful to someone.)