Could you make a Faraday cage with a different force law? Gauss' law depends on the mathematical form of the Coulomb force. However, the phenomena that static charge resides on the surface of a conductor, and that you can't have electric fields within a conductor or conducting shell, are usually given a heuristic explanation. Electrons are the moving species. They repel until they get as far away as possible, this being the surface of the conductor. Also, as long as they feel a repulsive force (whatever the mathematical nature of that force) they will redistribute until there is no net force. If you apply an external field, they will shift around to cancel it.
None of that seems to depend on the nature of the electrostatic force between the electrons.
So, is the heuristic argument good enough? Will any repulsive force do, or does it have to be a Coulomb force?
 A: First, I think it's right to revert your first sentence. The Gauss' law is more natural and elementary – and the $1/r^2$ Coulomb inverse square law is a consequence of the Gauss' law. In spacetimes of different dimensions, one naturally gets a different power law for the electrostatic force; Gauss' law is always right, however.
You don't have electric fields inside a stationary conductor because of Ohm's law, as you say. A nonzero $\vec E$ would mean a nonzero current density $\vec \jmath$ which would imply that the charges keep on redistributing, and the configuration would therefore fail to be stationary. When the fields stabilize, we inevitably have $\vec\jmath=0$ and therefore, due to Ohm's law, $\vec E=0$. And that's why the interior of metals shields you against the external electric fields – that's what's the Faraday cage is – but not quite the external magnetic fields.
Note that the argument in the previous paragraph didn't depend on any specific formula for any force. So of course that it would work in higher spacetime dimensions, for example, too. However, the argument did depend on the assumption that the conductor reaches some stationary configuration. 
You could design theories of mechanics – not really well-motivated by field theory (electrodynamics) – where the force between the charges (and, therefore, even the electric fields induced by charges) would be e.g. such that it would decrease with the velocity and it would be increasingly hard for the electrons to flow or stop etc. Or you could design some dependence on the distance so that the repulsion would strictly stop for electrons that are e.g. too close to each other, and you could then have pockets of electrons inside the metal that no longer repel. Or you could envision materials that don't obey Ohm's law for some other bizarre reasons (the force isn't proportional to $\vec E$, and so on). 
But none of these theories is true for the real-world metals. None of them is really compatible with any field-theory description of the electromagnetic phenomena. The classical electromagnetic theory really dictates everything about the electric and magnetic behavior of the vacuum, conductors, and other materials. This should have been said at the very beginning. There is no viable electromagnetic field theory in 3+1 dimensions in which the electrostatic force would be different than $1/r^2$. This power law may really be derived from the first principles. If the first principles are so different that $1/r^2$ cannot be derived, one shouldn't call the physical phenomena "electromagnetism" at all.
