The IceCube Neutrino Observatory has revealed the existence of sources of high-energy astrophysical neutrinos. However, identification of the sources is challenging because astrophysical neutrinos are difficult to separate from the background of atmospheric neutrinos produced in cosmic-ray-induced particle cascades in the atmosphere. The efficient detection of air showers in coincidence with detected neutrinos can greatly reduce those backgrounds and increase the sensitivity of neutrino telescopes. Imaging Air Cherenkov Telescopes (IACTs) are sensitive to gamma-ray-induced (and cosmic-ray-induced) air showers in the 50 GeV to 50 TeV range, and can therefore be used as background-identifiers for neutrino observatories. This paper describes the feasibility of an array of small scale, wide field-of-view, cost-effective IACTs as an air shower veto for neutrino astronomy. A surface array of 250 to 750 telescopes would significantly improve the performance of a cubic kilometer-scale detector like IceCube, at a cost of a few percent of the original investment. The number of telescopes in the array can be optimized based on astronomical and geometrical considerations.