Unfortunately, I can't present you with a silver bullet. I can definitely understand your frustration. Complex Analysis is hard for me to begin with (I'm taking a grad level course in it right now), and I'm pretty good with proofs in an algebra setting. It can be challenging subject matter, depending on the breadth of the course.
I learned proofs by taking a (required) class titled "Introduction to mathematical reasoning." There are textbooks with this title and I would highly recommend picking one up. I don't have a particular one in mind for you. Perhaps checking out some reviews on Amazon will help. Here's one such book. The idea in such a course is to present you with some of the classical problems in math that required rigor to prove like showing that there are infinitely many primes or Fermat's Little Theorem (I really loved that one). A course like this will make you comfortable with the most common ideas of proofs like finite sets, infinite sets and their cardinality, proof by induction, proof by contrapositive, proof by contradiction and many, many others.
Regarding epsilons and deltas: I think you really have to wrap around the fact that first you pick an epsilon, and then you can find a delta which makes the statement work. A textbook on math reasoning will definitely cover the paradigm "for all blank there exists some other blank." It's a very common theme. You should try not to be intimidated by the very sight of epsilons and deltas. =) Most of the time it's enough to write down what you're given methodically and what you're being asked to demonstrate will pop out. Perhaps you could give us an example of a proof that baffles you? I'd be happy to try and make it clearer.