Achieving ambitious reductions in greenhouse gases (GHG) is particularly challenging for transportation due to the technical limitations of replacing oil-based fuels. We apply the integrated assessment model MEDEAS-World to study four global transportation decarbonization strategies for 2050. The results show that a massive replacement of oil-fueled individual vehicles to electric ones alone cannot deliver GHG reductions consistent with climate stabilization and could result in the scarcity of some key minerals, such as lithium and magnesium. In addition, energy-economy feedbacks within an economic growth system create a rebound effect that counters the benefits of substitution. The only strategy that can achieve the objectives globally follows the Degrowth paradigm, combining a quick and radical shift to lighter electric vehicles and non-motorized modes with a drastic reduction in total transportation demand.