Gauss's law for induced electric and magnetic field Let us consider an accelerating charge, $Q$. As it is accelerating it would radiate energy in 
the form of EM waves, as per the classical postulates of EM theory. As such there would be induced electric fields let us consider a part of space where this charge $Q$ is not present. Now if I choose an imaginary enclosed surface in that part of space would the  electric flux through that surface sum out to  zero owing to absence of charge there? I meant to ask can we mathematically see whether it would sum up to zero thereby confirming Gauss's law even for induced electric fields.
what about magnetic flux?
I guess the most important thing as to why Gauss's law in case of static charges hold true is the inverse square variation of electric field due to static charges. But the electric field due to accelerating charges might not vary in such manner. 
Nextly, in apprehensions of answers which would use the equation of an EM  wave I would like to point out that while deriving those equations we assume that Gauss's law hold good even for induced electric fields. (I do doubt this assumption) and hence that might turn out to be a case where we use A to prove B and then again use B to ascertain A.
 A: I have posted an answer before, but, thinking about it for a while, deleted it in shame.
I still have no answer and even more questions, but OP and readers will probably enjoy this article on the subject: Notes on Gauss’s law applied for time varying electric field in vacuum, published on arXiv, 26 Jan 2015. It contains formal derivation of flux of electric field created due to movement of accelerating charge.
Add: also take a look on this topic Divergence of non conservative electric field
A: 
Now if I choose an imaginary enclosed surface in that part of space would the electric flux 
  through that surface sum out to zero owing to absence of charge there? 

Yes.

I meant to ask can we mathematically see whether it would sum up to zero thereby confirming 
  Gauss's law

No, we can't confirm Gauss's law this way.
To understand these answers, consider how you would go about calculating the total electric and magnetic fields for the accelerating point charge in the first place. This calculation would be similar to what you would do to derive The Larmor formula for radiation by an accelerating charge.
You would start by taking Maxwell's equations (forgive the Gaussian units):
$$
\nabla \cdot \vec B=0
$$
$$
\nabla \cdot \vec E=4\pi\rho
$$
$$
\nabla \times \vec E = \frac{-\partial \vec B}{c\partial t}
$$
$$
\nabla \times \vec B = \frac{4\pi\vec J}{c} +\frac{\partial \vec E}{c\partial t}
$$
and then plugging in the expression for the density and current of the point charge
$$
\rho(\vec x,t)= Q\delta(\vec x-\vec r(t))\;,
$$
$$
\vec J(\vec x,t)=Q\frac{d\vec r}{dt}\delta(\vec x-\vec r(t))\;,
$$
where $\vec r(t)$ is the position of the point change as a function of time (which sometimes has $d^2\vec r/dt^2$ non-zero since the charge accelerates).
Then you would manipulate Maxwell's equations to remove the $\nabla$ operators--I.e., you would solve the partial differential equations for the given density and current for obtain explicit expressions for
$$
\vec E(\vec x,t)
$$
and
$$
\vec B(\vec x,t)\;.
$$
And, now... you want to choose some finite volume in space and time, not containing the charge, and integrate the electric field over it... But the answer is guaranteed to be zero because one of the equations you used to solve for $\vec E$ in the first place is
$$
\nabla \cdot \vec E=4\pi\rho\;,
$$
which is
$$
\nabla \cdot \vec E=0
$$
in a volume not containing the charge, such that
$$
0=\int_{volume-not-containing-charge}\nabla\cdot \vec E=\int_{closed-surface-not-containing-charge}d\vec S\cdot \vec E
$$
A: Along with Timaeus and hft, I wonder what you would consider to be acceptable assumptions.  Usually Coulomb's law is taken to be less universal than Gauss' law, so one is usually more interested to derive Coulomb's law as a special case of Gauss' law for static charges rather than the other way around.  If you want to reverse that and start from Coulomb's law, then determine what the field is like for the accelerating charge, you need to know something about how disturbances in the field propagate.  As you point out, that typically means showing that the fields propagate according to the wave equation, but doing that without using Gauss' law is complicated.  Specifically, instead of the usual wave equation:  $$\nabla^2 \mathbf{E} = \mu_\circ \epsilon_\circ \dfrac{\partial^2 \mathbf{E}}{\partial t^2},$$
you ge an extra term: $$\nabla^2\mathbf{E} = \mu_\circ \epsilon_\circ \dfrac{\partial^2 \mathbf{E}}{\partial t^2}+\nabla(\nabla\cdot\mathbf{E}).$$
That assumes, of course, that Faraday's law and Ampère's law sill apply.
EDIT:  Note that this provides one of the strongest empirical tests of Gauss' law.  If the last term were not zero in empty space, the electromagnetic waves that are its solution would show some dispersion even in the vacuum.  The fact that no such dispersion is seen, even in waves coming from distant stars and galaxies, provides strong upper limits on how big any deviations from Gauss' law might be.
However, if you take as your premise that Ampère's law and the continuity equation (i.e. charge conservaton) apply, then Gauss' law is a necessary consequence. To see why, start with Ampère's law:
$$\mathbf{\nabla}\times\mathbf{B} = \mu_\circ \epsilon_\circ \dfrac{\partial \mathbf{E}}{\partial t}+\mu_\circ \mathbf{J}$$
take the divergence:
$$0 = \epsilon_\circ\dfrac{\partial \mathbf{\nabla}\cdot\mathbf{E}}{\partial t}+\mathbf{\nabla}\cdot\mathbf{J}$$
and apply the continuity equation $\nabla\cdot\mathbf{J} = -\dfrac{\partial \rho}{\partial t}$:
$$0 = \dfrac{\partial(\epsilon_\circ \nabla\cdot\mathbf{E}-\rho)}{\partial t}.$$
It follows that $\epsilon_\circ \nabla\cdot\mathbf{E}-\rho = const.$  Since Coulomb's law (or, if you prefer, Gauss' law) must obtain while the charge is at rest prior to accelerating it, we must have $const = 0.$ 
A: If you had Maxwell's other equations $$\vec{\nabla}\cdot\vec{B}=0,$$
$$\vec{\nabla}\times\vec{E}=-\frac{\partial\vec{B}}{\partial t},$$
$$\vec{\nabla}\times\vec{B}=\mu_0\left(\vec{J}+\epsilon_0\frac{\partial\vec{E}}{\partial t}\right),$$
then for smooth enough fields (enough that partials in different directions commute) you can take the divergence of both sides of the last equation to get:
$$0=\vec{\nabla}\cdot\left(\vec{\nabla}\times\vec{B}\right)=\mu_0\left(\vec{\nabla}\cdot\vec{J}+\epsilon_0\frac{\partial\vec{\nabla}\cdot\vec{E}}{\partial t}\right).$$
Thus, $0=\vec{\nabla}\cdot\vec{J}+\frac{\partial\epsilon_0\vec{\nabla}\cdot\vec{E}}{\partial t}$, so regardless of whether you want $\epsilon_0\vec{\nabla}\cdot\vec{E}$ to equal $\rho$, there is a conserved quantity $\epsilon_0\vec{\nabla}\cdot\vec{E}$, whose current/flux is measured by $\vec{J}$.
So you might as well take $\epsilon_0\vec{\nabla}\cdot\vec{E}=\rho$ if you have the other equations.  Mathematically, you have few other options.  You could postulate another additional form of charge that never moves, but then you lose the Lorentz Force Law, conservation of energy, and conservation of momentum.
So, what if you reject all of Maxwell's equations?  At some point it seems strange to call it electromagnetism, but you can write down any vector field you want and call it the electric field, pick another field, any one you want and call it the magnetic field, and the fact that they don't satisfy Maxwell's Equation, isn't a problem, ... mathematically.  And then indeed, as long as some charge somewhere isn't at rest, then you don't have to comply with electrostatics either since you can say that the one charge moving somewhere is responsible for whatever strange effects here you want to blame it for.
We can't get a mathematical result for free.  We have to use some inputs.  One person might want to use Liénard-Wiechert fields, and then show that they satisfy Maxwell's equation.  In that case they assumed Liénard-Wiechert and got Maxwell.  Someone else might assume Maxwell and try to show Liénard-Wiechert.  Someone else might want to assume a Lagrangian, and extremize it.  Someone else might want to start with a bunch of given solutions (fields) and look for the simplest equations that have those fields as solutions.
I can't tell what you want to assume, and mathematically you can't show anything without first assuming something.  Even mathematical theorems have assumptions/hypothesi (and mathematical theories have axioms).  If you won't accept wave solutions, then maybe you won't accept any source free solution to Maxwell.
This historical answer is a bit like the example of taking many solutions.  Electrostatics experiments gives both the inverse square law and it can also give $\epsilon_0\vec{\nabla}\cdot\vec{E}=\rho$.  Sprinkling iron fillings can motivate solutions where $\vec{\nabla}\cdot\vec{B}=0$.  Moving magnets through wires, or just changing the strength of a magnetic field in a region in general gives solutions to $\vec{\nabla}\times\vec{E}=-\frac{\partial\vec{B}}{\partial t}$.  Changing an electric field (say by charging a capacitor) or transporting a charge (making a current) could produce a circulating $\vec{B}$ field, so motivate: $\vec{\nabla}\times\vec{B}=\mu_0\left(\vec{J}+\epsilon_0\frac{\partial\vec{E}}{\partial t}\right)$.  But then you'd have to verify the applicability of the combined laws to situations beyond those inspirational situations.
And that's what we did. And we found a whole range of phenomenology explained by Maxwell's Equation, and we call it Classical Electrodynamics. It's isn't a mathematical requirement, it a physical hypothesis, a physical theory. And it's wrong in the sense that it doesn't hold for all possible phenomenological situations (witness the photoelectric effect, the blackbody spectrum, etc.).
So let's go back to the electrostatics experiments, how they were consistent with both the inverse square law and $\epsilon_0\vec{\nabla}\cdot\vec{E}=\rho$. Since the latter one gives the conserved quantity that $\vec{J}$ is the flux of, it makes sense to hypothesize that it is the correct equation.  But the justification is partly that the whole system of Maxwell-Lorentz predicts things like electromagnetic waves which were observed after they were predicted.  In your post you didn't want us to use wave solutions.  We've seen wave solutions in the lab.  Radio waves weren't even a speculation, they were predicted because of these equations.
We use Maxwell's equations because for a range of phenomena, they work when other things either outright fail or are just too complicated.
A: A charge cannot come out of nowhere. The various possibilities are:


*

*The charge must have existed beforehand in which case most regions of space would have had an electric field already, or

*the charge was created as part of pair of opposite charges, in which case the electric field lines would curve back to the opposite charge, and any flux entering the Gaussian surface would also leave it (this argument also applies to magnetic fields, which arise from dipoles), or

*the charge accelerated in from infinity, in which case it is possible to have a region of space that is ignorant of the charge and its field.


The third case, of a charge in hyperbolic motion, is treated by Joel Franklin and David Griffiths in their article "The fields of a charged particle in hyperbolic motion," published in Am. J. Phys. 82, 755 (2014). They conclude that the electric field is kinked in such a way that Gauss' Law remains valid. 
Of course, their treatment is based off of Maxwell's Laws, and may not be valid in some other form of electrodynamics, but they have at least shown that usual Maxwellian electrodynamics is consistent.
