How can we let a car, of which the front (and rear) wheels are tightly connected by a solid rod, make a turn? Consider a car with four equal wheels. The front (and rear) wheels are tightly connected by a solid rod (i.e. both the front and rear wheels rotate with the same angular velocity). 
How can we let this car make a turn? The wheels on the right (or left) side must rotate with the same angular velocity as the wheels on left (or right) side, that's for sure. 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)?
What are the possibilities?
 A: 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.
A: some racing karts have solid rear axles. they make turns so sharp that most of the kart's weight shifts to the outside tire, allowing the inside tire to break traction with the pavement and skid lightly through the turn. I do not know if this trick would work for your front axle, however.
