We introduce the concept of 'dynamical phase coexistence' to provide a simple solution for a long-standing problem in theoretical ecology, the so-called "savanna problem". The challenge is to understand why in savanna ecosystems trees and grasses coexist in a robust way with large spatio-temporal variability. We propose a simple model, a variant of the Contact Process (CP), which includes two key extra features: varying external (environmental/rainfall) conditions and tree age. The system fluctuates locally between a woodland and a grassland phase, corresponding to the active and absorbing phases of the underlying pure contact process. This leads to a highly variable stable phase characterized by patches of the woodland and grassland phases coexisting dynamically. We show that the mean time to tree extinction under this model increases as a power-law of system size and can be of the order of 10,000,000 years in even moderately sized savannas. Finally, we demonstrate that while local interactions among trees may influence tree spatial distribution and the order of the transition between woodland and grassland phases, they do not affect dynamical coexistence. We expect dynamical coexistence to be relevant in other contexts in physics, biology or the social sciences.