If molecules of air were very slow moving, and the cube came zipping through, then the cube would cut a 1 m x 1 m square tunnel of vacuum through the air, which would slowly be filled in by air molecules from above and below moving in to it.
So as long as the cube moves faster than air molecules, some of that tunnel will stay evacuated behind the tube. How fast do air molecules move? Still air at STP has its air molecules zipping around randomly with each species of air molecule having a Maxwell-Boltzmann distribution of velocities. From http://www.newton.dep.anl.gov/askasci/chem03/chem03448.htm we see an "average" air molecule is moving at around 500 m/s.
But in a thermal distribution, LOTS of air molecules are moving faster than the average, but at higher velocities the distribution falls off quite steeply. The Maxwell-Boltzmann distribution shows the probability distributions for thermal air molecule velocities. Looking at the CDF's, we can see that nearly all the molecules have a velocity within a factor of 3 or 4 times the average velocity.
Then if the 1 m cube were moving at 2000 m/s, we would expect a pyramid shaped region on the back of the pyramid with pyramid peak about 0.5 m behind the cube, within which the density of air would be less than about 1% of STP.
So 2000 m/s, 2 km/s, 7200 km/hr should do the trick. For reference this is about 7 times the speed of sound at sea level.