In short, the car cannot make a turn without one wheel skidding in this case if the axle rigidly links both wheels and forces the constraint you speak of.
Do we, for example, have to give full gas to make both wheels on one side slip, while the wheels on the other side are not slipping but rolling (by placing the wheels on one side on a different material than on the other side)?
Something like this is true; it is the role of the Differential Gearbox to allow both wheels to spin at different angular speeds such that their average angular speed is held constant (and equal to a fixed multiple of that of the driveshaft) and also so that torque can be imparted to both wheels notwithstanding the different angular speeds.
Fun Fact: Although the Differential's name refers only to different angular speeds and has nothing to do with differential geometry, the Differential is an essential device in realizing a South Pointing Chariot, which can be used in an elegant intuitive explanation of the notion of parallel transport and connexion in geometry, see:
Mariano Santander, "The Chinese South-Seeking chariot: A simple mechanical device for visualizing curvature and parallel transport", Am. J. Phys. 60 #9 pp782-787 (1992)
Indeed, a lone wheel of nonzero width cannot make a turn without skidding for the same reasons you have identified, unless the wheel has a conical profile of the correct angle. This latter phenomenon is much less extreme because the path curvature varies much less over the tyre's width than it does between wheels. Indeed the elastic deformation wrought in the tyre owing to the nonuniform path curvature across the tyre's width is what begets the steering torque imparted by a wheel tracking a curved path on the car for steering mechanisms. This unavoidable slight skid is what leads to inevitable tyre wear from turns. It is also highly apparent if you drive slowly on very polished surfaces, such as polished concrete in some underground carparks; as you turn, you can hear a loud, squeaky-rubber kind of sound rather like one hears in stroking a blown up rubber ballon.
