If I have an infinite plate with the surface charge of sigma. I know that my electric field is constant $2\pi\sigma$ (using Gauss's law). If I build the Gaussian surface above the plate the charge inside it would be 0 and as a result of Gauss's law ($E \cdot da = 4 \pi Q_\text{inside}$) the electric field should be 0 as well.
Why do we need symmetry to use Gauss's law? and why doesn't it work in the example above?
You have two questions, and they have different answers. First of all, let's be clear about what Gauss's law is in integral form:
$$ \int \vec{E} \cdot \mathrm{d} \vec{A} = \frac{Q_\mathrm{encl}}{\epsilon_0} $$
In words: the total flux integrated over a closed surface is equal to the charge enclosed in that surface, divided by the permittivity of free space $\epsilon_0$. Now, you attempt to apply this to an infinite sheet by drawing a closed surface which does not enclose the plane of charge at all. As you note correctly, this causes the right-hand side of the above equation to be zero, which seems to imply the left hand side is also zero. However, the left hand side can be zero even if $\vec{E} \neq 0$. Usually the way we do Gauss's law for the infinite sheet of charge is to imagine a small, thin box, so let's consider this shape. We know that (from other calculations) $\vec{E}$ points in the $\hat{z}$ direction, so the sides of the box do not contribute since there the field is perpendicular to to the area vector $\mathrm{d} \vec{A}$. So we worry only about the top and bottom of the box. In addition, the electric field will be constant across both areas of the box. This allows us to skip the integral part, and just multiply by the actual area of the surface. Let's write this as: $$ \int \vec{E} \cdot \mathrm{d} \vec{A} = \vec{E}_\mathrm{top} \cdot \vec{A}_\mathrm{top} + \vec{E}_\mathrm{bottom} \cdot \vec{A}_\mathrm{bottom} $$
We can simplify this a lot too. We know that the electric field is constant $\vec{E}_\mathrm{top} = \vec{E}_\mathrm{bottom} = \vec{E}$. We also know that the two areas are equal (because it's an imaginary box anyway so let's just say they are). Then carrying out the dot product we get
$$ \int \vec{E} \cdot \mathrm{d} \vec{A} = E A \cos{\theta_\mathrm{top}} + E A \cos{\theta_\mathrm{bottom}} $$ Alright. But we draw the box such that the electric field shoots straight through it, meaning that we will get the electric field perpendicular to the surface in both cases. However, we always define the angle of the surface area vector as outward, which means that we have $\theta_\mathrm{bottom} = \pi$ and $\theta_\mathrm{top} = 0$. One of the area vectors is parallel to the electric field; one of the area vectors is anti-parallel. So one of them gets a negative sign, and we get: $$ \int \vec{E} \cdot \mathrm{d} \vec{A} = E A - E A = 0 $$ So Gauss's law holds, even though $ \left| \vec{E} \right| \neq 0$.
You asked why we need symmetry. If you examine my above calculation carefully you should see that symmetry was key to my ability to do the integral without actually having to integrate it--since $\vec{E}$ was not a function of position, I was able to pull it out of the integral: $$ \int \vec{E} \cdot \mathrm{d} \vec{A} = \vec{E} \cdot \int \mathrm{d} \vec{A} $$ Without this ability--which comes entirely from the fact that I know $\vec{E}$ does not depend on x-y position, because how could it?--I would have to know the form of $\vec{E}$ functionally before I started the calculation. Since the whole point of the calculation is to determine $\vec{E}$, I would be kind of sunk! This is why the integral form of Gauss's law is generally of limited use for determining electric fields outside of, off the top of my head, three cases. (Spheres, infinite sheets, and infinity cylinders/line charges.)
