When is it okay to ask your advisor solution to a technical problem? For example, if (hypothetically speaking) I am stuck on proving a theorem, is it okay to ask my academic advisor some help for next step? My approach has been, "this is what I have tried, I am stuck here...can you point out how I can continue". But the amount of time that it takes the professor to reply is stressing me out, I am afraid that he is getting exasperated at my question.

What makes thing a bit worse is that the prof says flat out he likes people who are able to solve problems independently. But he also has a reputation of being a fast replier to student emails regarding problems arising in his course. I wonder what he expects of me.

So what is considered appropriate to ask your advisor without pushing him to the limit of having to solve the problem himself. Ultimately I am worried about looking totally incompetent. Is there some way for me to not appear totally incompetent?
Your approach to asking -- "this is what I have tried, I am stuck here...can you point out how I can continue?" -- is the right one. Without knowing how difficult of a problem you have gotten stuck on, and how often you ask for help, it is very hard for us to judge how your advisor will interpret your request.

That said, in general I very much appreciate it when my graduate students and postdocs let me know when they get stuck on some step of a research project. My students and I are collaborators after all, and if I can help them get going again, or alternatively if I can recognize that we've been heading down a dead-end, this is very much to everyone's benefit. 

Of course, they should not be coming to me with trivial problems: "I can't get this expression to format properly in LaTeX" or "I don't know how to compute the Jacobian matrix for this function", nor would I want to get these requests on a daily basis. But if a competent student has made a serious effort to solve a problem and is still stuck, I'd like to know about it and to help if at all possible.