The tires of a car execute pure rolling. Therefore, the work done by friction on the tires (and hence the car) is zero. If no external work is done, how does a car's kinetic energy increase?
The increase in the car's kinetic energy comes from the internal energy of the car, stored, for example, in its gasoline or batteries.
The engine exerts torque over the wheels, which are prevented by the friction from simply rotating in place. The reaction from the ground on the car (wheels) makes it move faster.
You are mixing up two different things.
If we have two surfaces sliding over each other, and there is a non-zero coefficient of friction between them, then energy is dissipated as friction. This lost energy is just the distance the surfaces have slid multiplied by the frictional force. In the case if the (ideal) wheels then you are quite correct that because no sliding occurs the energy lost to friction is zero.
But all this means is that no energy is lost to friction. The car and the road exert an equal and opposite force on each other, so as the car moves external work is done by the road on the car. The non-slipping of the car tyres just means all that work goes into the kinetic energy of the car and none is lost as friction.
The answer is that a static frictional force can do work.
Consider the case of you sitting in a car which is accelerating.
The seat has no back and you are not moving relative to the seat.
Now consider you as the system.
You have three forces acting on you.
In the vertical direction your weight and the normal reaction due to the seat cancel out and you are left with the horizontal static frictional force which is accelerating you and moving with you.
It is the work done by that static frictional force which causes you to increase your kinetic energy.
Of course the ultimate source of the increase in kinetic energy is the chemical energy stored in the fuel which the engine converts into a useful form.
Update as a result of a discussion with the OP.
Going back to the car with you sitting on the seat.
What does an observer on the road see?
The observer sees a constant horizontal static frictional force due to the seat acting on you.
The observer sees that force moving along with the same velocity as the car in the same way, as the observer would see somebody on the car pushing you from behind to accelerate you, or accelerate you if the seat with a frictionless bottom was place on the ground and somebody was pushing you.
In all instances there is a force acting on you and as the force undergoes a displacement work is being done by that force.
Going back to your question.
The observer on the road sees the car with a horizontal frictional force acting on the car (tyres).
That observer sees that force undergo a displacement hence that force has done work.
It matters not how that horizontal frictional force arose the fact is that the car is subjected to a constant horizontal force which we know is due to static friction.
That force accelerating the car could have been due to somebody pushing the car where the point of contact of the force is the car and so the person applying the force is not moving relative to the car.
In accelerating the car from rest, static friction DOES positive work which is the change in linear kinetic energy of the car. BUT it also does negative work on the wheel(it creates counter torque) which decreases the rotational kinetic energy of the wheel. So, the NET work done by static friction is 0. It simply converts some part of the rotational kinetic energy of the engine to linear kinetic energy until the condition of no slipping is met. That makes sense if you think about it because the road does not have energy to transfer to the system.