I belonged to a school education system where we were made to do lots of different problems, but we were never told to try and understand the underlying theory behind the problems. This made me scared of math. What I basically had was a cookbook of a variety of wonderful recipes without realizing why I needed to add salt or sugar to a dish. May be you are facing the same problem? May be you are learning all these different techniques to solve problems without really understanding the theory behind why the problems can be solved using those techniques? Hence, because you don't understand the theory behind the techniques, once you get a problem that cannot be solved using the techniques you are familiar with, you get stuck.
While I agree with glebovg that trying to develop an intuition for how to write proofs is essential, I feel that you should make the effort to start reading proofs first. For instance, a book that really helped me understand Calculus was Spivak's Calculus. Try going through the proofs there, and learn the underlying theory. This is coming from someone who was in your position not too long ago.
I encourage you to read books that emphasize problem solving, but at some point you will just have muster the courage to open a book with proofs, and read through it.
Also, the issue of memorization is kind of a slippery slope. You will find that often even when you are trying to understand the theory, you will just have to memorize some computational techniques here and there. I think Terry Tao has a good post where he addresses the issue of memorization. I agree with him that certain basic things have to be memorized. For instance, you will have to memorize what the axioms of a group or a field are. I think memorization and understanding go hand in hand. Certainly your goal should not be to only memorize techniques to solve problems.
Here is more advice from a master:
http://terrytao.wordpress.com/career-advice/solving-mathematical-problems/
http://terrytao.wordpress.com/career-advice/there%E2%80%99s-more-to-mathematics-than-rigour-and-proofs/
http://terrytao.wordpress.com/career-advice/there%E2%80%99s-more-to-mathematics-than-grades-and-exams-and-methods/
http://terrytao.wordpress.com/career-advice/does-one-have-to-be-a-genius-to-do-maths/
All the best!