We report on the detection of a very rapid TeV gamma-ray flare from BL Lacertae on 2011 June 28 with the Very Energetic Radiation Imaging Telescope Array System (VERITAS). The flaring activity was observed during a 34.6 minute exposure, when the integral flux above 200 GeV reached (3.4 + or - 0.6) x 10 super(-6) photons m super(-2) s super(-1), roughly 125% of the Crab Nebula flux measured by VERITAS. The light curve indicates that the observations missed the rising phase of the flare but covered a significant portion of the decaying phase. The exponential decay time was determined to be 13 + or - 4 minutes, making it one of the most rapid gamma-ray flares seen from a TeV blazar. The gamma-ray spectrum of BL Lacertae during the flare was soft, with a photon index of 3.6 + or - 0.4, which is in agreement with the measurement made previously by MAGIC in a lower flaring state. Contemporaneous radio observations of the source with the Very Long Baseline Array revealed the emergence of a new, superluminal component from the core around the time of the TeV gamma-ray flare, accompanied by changes in the optical polarization angle. Changes in flux also appear to have occurred at optical, UV, and GeV gamma-ray wavelengths at the time of the flare, although they are difficult to quantify precisely due to sparse coverage. A strong flare was seen at radio wavelengths roughly four months later, which might be related to the gamma-ray flaring activities. We discuss the implications of these multiwavelength results.