The understanding of spin dynamics and relaxation mechanisms in clean graphene, and the upper time and length scales on which spin devices can operate, are prerequisites to realizing graphene-based spintronic technologies. Here we theoretically reveal the nature of fundamental spin relaxation mechanisms in clean graphene on different substrates with Rashba spin-orbit fields as low as a few tens of μeV. Spin lifetimes ranging from 50 picoseconds up to several nanoseconds are found to be dictated by substrate-induced electron-hole characteristics. A crossover in the spin relaxation mechanism from a Dyakonov-Perel type for SiO2 substrates to a broadening-induced dephasing for hBN substrates is described. The energy dependence of spin lifetimes, their ratio for spins pointing out-of-plane and in-plane, and the scaling with disorder provide a global picture about spin dynamics and relaxation in ultraclean graphene in the presence of electron-hole puddles.