What happens when I use gradient descent over a zero slope? Let us assume my cost function such that its slope rises from point A at z=2 to B at z=4; stays constant till C at z=4; falls to D at z=1; rises to E at z=5.

If I choose my starting point between point B and C, differential of the cost function will be 0 (because slope is 0). Hence theta will never change its value.
How, then, will my function reach the minimum at D?
 A: It won't -- gradient descent only finds a local minima*, and that "plateau" is one.
However, there are several ways to modify gradient descent to avoid problems like this one. One option is to re-run the descent algorithm multiple times, using different starting locations for each run. Runs started between B and C will converge to z=4. Runs started between D and E will converge to z=1. Since that's smaller, you'll decide that D is the (best) local minima and choose that value.
Alternatively, you can add a momentum term. Imagine a heavy cannonball rolling down a hill. Its momentum causes it to continue through small dips in the hill until it settles at the bottom. By taking into account the gradient at this timestep AND the previous ones, you may be able to jump over (smaller) local minima. 

* Although it's almost universally described as a local-minima finder, Neil G points out that gradient descent actually finds regions of zero curvature. Since these are found by moving downwards as rapidly as possible, these are (hopefully) local minima, though it can settle anywhere the error surface is flat, as in your example. 
A: Simple answer: it won't. 
Gradient descent climbs down a hill. If it reaches a plateau, it considers the algorithm converged and moves no more. 
If you think that this is a fault of gradient descent, one should know that multi-modal problems are very difficult and outside of a fine grid search (which can easily be prohibitively computationally expensive and requires you to pinpoint a region where the solution must be), there's no real generic algorithm for multi-modal problems. 
A simple method for handling this is restart your hill climbing algorithm (sorry, I'm used to the maximization terminology, rather than the minimization) several times from random starting points and use the best solution you get. If the problem is uni-modal, all your solutions should be relatively close. If the problem is multi-modal, hopefully one of your random start points was on the correct hill. 
A: There's only one thing you need to know about gradient descent. It is complete and utter garbage, and an absolutely horrible algorithm which should not even be considered unless there are at least hundreds of millions of variables, in which case don't expect it to work well, except when solving the same problem over and over again, for which good values of learning rates have been found. it is a poor man's unsafeguarded version of steepest descent, which even in safeguarded form is bad. You'll be much better of with a trust region or line search Quasi-Newton method. Don't write your own.  
Gradient descent is a misnomer. it may not even descend. Safeguarded algorithms, which use trust regions or line searches, either descend, or terminate if unable to descend. The "learning rates", in some manner of speaking, are adaptively determined by the algorithms based on what they encounter.They won't overshoot as gradient descent can, and can automatically speed up when warranted. Gradient descent wasn't even a good algorithm a century ago.       
A protracted zero slope region could cause problems for any optimization algorithm, unless it is a rigorous global optimization algorithm. Rigorous global optimization algorithms, for instance based on branch and bound, do exist (I'm not talking about genetic algorithms and other heuristic rubbish, which are the moral equivalent of gradient descent), but may not succeed in solving a problem if it is too large or too difficult, and may not accept all functions. Your local optimization algorithm algorithm should check 2nd order optimum conditions if possible. That will distinguish a local minimum from a local maximum or saddlepoint.
As stated in other answers, it is a good idea to run a local optimization algorithm with several different starting values.  But that algorithm should generally not be gradient descent. 
In my opinion, Andrew Ng has done a great disservice to people by teaching them gradient descent. People think they know how to optimize, when they know no more about how to optimize or optimization than a 3 year old kid "driving" with a placebo steering wheel a plastic car attached to the front of a supermarket shopping cart does about driving.   (And for the benefit of a certain commenter who claimed that my providing an explicit formulation of his (her) problem as a constrained optimization problem, said that I had only repeated his(her) problem, and that imposing constraints after the fact was not a good way to solve an optimization problem, and then refused to change his(her) view after I explained how constrained optimization works, which is not imposing constraints "after the fact", and that there is a very well-developed theory for constrained optimization and practical ready to go software to solve constrained optimization problems, then he (she) downvoted that very detailed, thoughtful, and friendly answer, and wrote that we can both agree that I didn't answer his(her) question) there is practical ready to go software to solve constrained optimization problems, which apparently many people who "learned" optimization from Andrew Ng et al have no idea even exists.  And non-specialists are not going to do a good job of writing their own constrained optimization software (or unconstrained optimization software either).  Andrew Ng does people a disservice by making them think they can.  Nor is there a need to do so, since good optimization software exists, although R is littered with not so good optimization software. Any improvements on good off the shelf software to take advantage of special problem structure, for instance, are unlikely to be made effectively by someone other than an exeprt in numerical optimization and numerical analysis.
