Cultural processes, as well as the selection pressures experienced by individuals in a population over time and space, are fundamentally stochastic. Phenotypic variability, together with imperfect phenotypic transmission between parents and offspring, has been previously shown to play an important role in evolutionary rescue and (epi)genetic adaptation of populations to fluctuating temporal environmental pressures. This type of evolutionary bet-hedging does not confer a direct benefit to a single individual, but can instead increase the adaptability of the whole lineage. Here we develop a population-genetic model to explore cultural response strategies to temporally changing selection, as well as the role of local population structure, as exemplified by heterogeneity in the contact network between individuals, in shaping evolutionary dynamics. We use this model to study the evolutionary advantage of cultural bet-hedging, modeling the evolution of a variable cultural trait starting from one copy in a population of individuals with a fixed cultural strategy. We find that the probability of fixation of a cultural bet-hedger is a non-monotonic function of the probability of cultural memory between generations. Moreover, this probability increases for networks of higher mean degree but decreases with increasing heterogeneity of the contact network, tilting the balance of forces toward drift and against selection. These results shed light on the interplay of temporal and spatial stochasticity in shaping cultural evolutionary dynamics and suggest that partly-heritable cultural phenotypic variability may constitute an important evolutionary bet-hedging strategy in response to changing selection pressures.