The prospect of transporting spin information over long distances in graphene, possible because of its small intrinsic spin-orbit coupling (SOC) and vanishing hyperfine interaction, has stimulated intense research exploring spintronics applications. However, measured spin relaxation times are orders of magnitude smaller than initially predicted, while the main physical process for spin dephasing and its charge-density and disorder dependences remain unconvincingly described by conventional mechanisms. Here, we unravel a spin relaxation mechanism for non-magnetic samples that follows from an entanglement between spin and pseudospin driven by random SOC, unique to graphene. The mixing between spin and pseudospin-related Berrya's phases results in fast spin dephasing even when approaching the ballistic limit, with increasing relaxation times away from the Dirac point, as observed experimentally. The SOC can be caused by adatoms, ripples or even the substrate, suggesting novel spin manipulation strategies based on the pseudospin degree of freedom.