Using the definition of electric flux, and knowing that the electric flux through a closed surface is proportional to the charge enclosed (that proportionality constant being $ \frac{1}{\epsilon_0} $).
One can calculate this proportionality constant using Coulomb's law and a charge at the centre of a symmetrical sphere.
$ \Phi = \frac{Q}{4 \pi \epsilon_0 r^2} 4 \pi r^2 = \frac{1}{\epsilon_0} Q $
Would it be possible to find the proportionality constant if we didn't know Coulomb's law?
It seems that, via the divergence theorem,
knowing that the electric flux through a closed surface is proportional to the charge enclosed
amounts to knowing everything about Coulomb's law except for the value of $\epsilon_0$. If you knew that much, you could measure the proportionality constant by placing two particles of known masses and charges a known distance apart and measuring the acceleration of either. Then you'd know the proportionality constants in both Coulomb's and Gauss's laws (which, as you noted above, are related by a constant factor of $4 \pi$).
I think @mpc wanted to say that $$\oint \vec E \cdot d\vec a = \int_V (\vec \nabla \cdot \vec E)da$$
But I had "found" the Gauss law using Electric displacement but I worry the expression isn't completely same, if you assume that you don't know any about Coulomb's law and electric displacement both then I can't make an assumption write now. But it works well for matters (material).
$$\vec D = \epsilon \vec E$$ $$\phi = \oint \vec E \cdot d\vec a=\oint \frac{\vec D}{\epsilon}\cdot d\vec a=\dfrac{q_{f_{enc}}}{4\pi r^2\epsilon}4\pi r^2=\dfrac{q_{f_{enc}}}{\epsilon}$$ $\epsilon=\epsilon_0$ for outside material. But in material $\epsilon=\epsilon_0\epsilon_r$.
I found this lab document, which instructs students to measure the force between two capacitor plates and use that to determine $\epsilon_{0}$.
Before I found the document, I was writing my own idea that could be done in principle. I'll write it here anyways. The idea is to consider a charged ball hung on a string and placed between two capacitor plates.
First, charge the ball by connecting a wire to it and sending a current $I$ for some time $\Delta t$. Using an ammeter you can find $I$, and then you can calculate its total charge by taking $q_{\text{ball}} = I\cdot\Delta t$.
Next, charge the capacitor plates the same way by sending a current $I$. Measure the current with an ammeter, and we find the charge density on each plate to be $\sigma_{\text{plate}} = I\cdot\Delta t / \text{Area}$.
Now by testing the force on the ball for various values of $\sigma_{\text{plate}}$ and $q_{\text{ball}}$, you can experimentally determine that the force $F$ is linearly proportional to $q_{\text{ball}}$ and $\sigma_{\text{plate}}$. This tells us that the force on the ball is $$ F = \frac{q_{\text{ball}}\sigma_{\text{plate}}}{\alpha(x)} $$ and $1/\alpha(x)$ is some constant of linear proportionality that may depend on the location where your charged ball is placed between the two plates. By determining the charge placed on your ball, the charge on your plates, and the force on the ball, you can calculate the value of $\alpha(x)$.
Notice, however, that at this stage we don't know whether $\alpha(x)$ is the same as $\epsilon_{0}$. For this, you need to use Gauss's law to deduce that $E = \sigma_{\text{plate}}/\epsilon_{0}$ and thus $F = q_{\text{ball}}\sigma_{\text{plate}}/\epsilon_{0}$ is the force on the ball. But since $F = q_{\text{ball}}\sigma_{\text{plate}}/\alpha(x)$, it follows $\alpha(x) = \epsilon_{0}$. So an experimental measurement of $\alpha(x)$ gives an experimental measurement of $\epsilon_{0}$.
