How is adding a charge outside a Gaussian surface consistent with Gauss' Law? The electric field of an infinite line charge with a uniform distribution of charge could be calculated using Gauss's law. If you then add a charge outside of the constructed Gaussian surface, the amount of charge enclosed $Q$ remains the same. Therefore the calculation of the electric field $\mathbf E$ should be the same as well.
But why does the charged object not influence the electric field?
 A: 
Therefore the calculation and the E calculated would be the same as well.

No. It would not be. Even though $Q_\text{enclosed}$ remains the same (and so does the electric flux), the electric field will be affected.
I assume you're getting this wrong by using the "simplified" Gauss' Law. In the case of an infinite uniform conductor, you can correctly make the simplification that $\displaystyle \oint \mathbf{\vec E}\cdot \mathrm d \mathbf{\vec A}=EA$. This is only true because $\bf\vec E$ is constant (this is a neat case of symmetry). However, by introducing a charge outside the infinite conductor, the net electric field is no longer constant, in which case $\displaystyle \oint \mathbf{\vec E}\cdot \mathrm d \mathbf{\vec A}\neq EA$.

But why does the charged object not influence the electric field?

It does influence the field. It does not influence the net flux, but just because the net flux is unaffected doesn't mean the electric field isn't.
A: 
If you then add a charge outside of the constructed Gaussian surface, the Q enclosed remains the same. Therefore the calculation and the E calculated would be the same as well.

This is incorrect. Gauss’ law only tells you about the net flux. It does not tell you about the E field. So, indeed, adding a charge outside the surface will not change the net flux, but it can and does change the field.
The only way that you can use Gauss’ law to go from net flux to field is in cases where there is a high degree of symmetry such that there can be only one possible value of the field that both satisfies Gauss’ law and the symmetry. In your example, there is such symmetry without the charge, but adding the charge removes the symmetry.
After removing that symmetry there are many configurations of field that are consistent with the net flux, but only one of those is the actual field. Which one cannot be determined by Gauss’ law alone.
