Let's say we consider an electric field in a vacuum where the fields lines are parallel but the fields strength varies with distance, and then consider a cube in this space as our Gaussian surface. Since the field strength varies at the 2 opposing faces of the cube where the field lines can contribute to the flux, the flux through the cube must be non-zero. But Gauss's dictates that for non-zero flux, the surface must contain charges within it. How is this possible in this case?
The electric field configuration you describe is not possible.
For a loose explanation, try to visualize the field lines you're describing. The strength of the electric field is related to the density of the field lines, so in your picture, the field lines must get closer together or further apart - but how could they do this if they are parallel?
If you understand and accept that positive/negative charges are the only local sources/sinks of the electric field (i.e. field lines can only "start" on positive charges and "terminate" on negative charges), then Gauss' law follows as a mathematical theorem.
If you don't accept that as a premise, then all I can tell you is that it is supported by a mindblowingly vast mountain of evidence, and that it is on as solid a scientific footing as it's possible to have.
Consider an electric field in a vacuum where the fields lines are parallel but the fields strength varies with distance.
No such field exists.
You’re talking about $\vec E=E_z(z)\hat z$. Its divergence is nonzero, unless $E_z(z)$ is a constant, and you said it isn’t. But a nonzero divergence implies that there is a nonzero charge density in that “vacuum”, which is a contradiction.
I support @J Murray answer. The strength of an electric field in a region of space is associated with the density of the field lines in the region. The lines themselves with arrows indicate the direction of the field in the region. It is impossible to have lines that are both parallel and of varying density. A field represented by parallel lines has to be uniform.
Hope this helps