Red supergiants (RSGs) are a He-burning phase in the evolution of moderately high mass stars (10-25 solar masses). The evolution of these stars, particularly at low metallicities, is still poorly understood. The latest-type RSGs in the Magellanic Clouds are cooler than the current evolutionary tracks allow, occupying the region to the right of the Hayashi limit where stars are no longer in hydrodynamic equilibrium. We have discovered four Cloud RSGs in this region that display remarkably similar unusual behavior. All of them show considerable variations in their V magnitudes and effective temperatures (and spectral types). Two of these stars, HV 11423 and [M2002] SMC 055188, have been observed in an M4.5 I state, considerably later and cooler than any other supergiant in the SMC. These stars suffer dramatic physical changes on timescales of months - when they are at their warmest, they are also brighter, more luminous, and show an increased amount of extinction. This variable extinction is characteristic of the effects of circumstellar dust, and can be connected with sporadic dust production from these stars in their cooler states. We suggest that these unusual properties are indicative of an unstable (and short-lived) evolutionary phase not previously associated with RSGs, and consider the implications such behavior could have for our understanding of the latest stages of massive star evolution in low-metallicity environments.