The answer to your question depends on precisely how it is interpreted. In my opinion, the clearest way of understanding a car driving on the road does in fact have the engine doing work on the car, but it is possible to define the system involved such that this is is not so. However, under this interpretation, the engine does no work on the car regardless of whether or not the tires are slipping.
To explain this distinction, I'll first give an example of work, then talk a little about work on the driving car, then finally discuss no-slip tires. I think this is a fairly-tricky issue, so please excuse the length of my response.
At Anna's request, let's assume no air drag, no internal friction, and no slipping. If the car is moving at a constant velocity, then the engine can be turned off, allowing the car to coast. There is clearly no work done and no change in energy in this scenario, so we'll talk about what happens as the car accelerates.
Work
In physics, "work" is a way of transferring energy into or out of a system. We say that a force does work on a system, thus adding energy to it. Work is defined by the equation
$$\textrm{d}W = \vec{F}\cdot \textrm{d}\vec{x}$$
The left hand side, $\textrm{d}W$, means "a small amount of work done". On the right hand side, $\vec{F}$ is the force that is doing the work, and $\textrm{d}\vec{x}$ is the movement of the part of the system where the force is applied. This does not particularly look like a change in energy, but it is possible to show, using Newton's laws, that work, as defined above, turns out to be the same as the change in kinetic energy induced by the force. (see work-energy theorem)
We need to keep in mind for later that although work done on a system induces a change in its kinetic energy, not all changes in kinetic energy are due to work being performed. For example, if I have a gerbil in a cage, and the gerbil starts running, the cage didn't go anywhere, so $\textrm{d}\vec{x} = 0$ for the system (gerbil + cage), so the work done on the cage/gerbil system is zero. Nonetheless, it gained kinetic energy. This is an internal conversion of energy from chemical energy in the gerbil to kinetic energy.
For an example of work, suppose you put your car in neutral and I stand behind it and push. If I push with a force of $100$ newtons, I do $1$ joule of work for each centimeter the car moves. In this example, $\textrm{d}W = 1 \textrm{J}$, $\vec{F} = 100 \textrm{N}$, and $\textrm{d}\vec{x} = 1 \textrm{cm}$. The "$\cdot$" symbol means the vector dot product. As long as the force and the motion are in the same direction, this is the same as normal multiplication (but if the force is at an angle to the motion, the work goes down; we won't worry about this in the rest of the answer). This work is the change in the kinetic energy of the car; the car speeds up some while I push.
It's important to define the system you're doing work on. In the example above, I considered the system to be your car. Then I applied an external force with my body. In an alternative view, we could define a system that consists of the car and me together. Then I didn't do any work on the system at all since, by definition, only external forces can do work. Finally, we might consider the system to be just the back half of the car. In this case, I'm still the external force and I did the same amount of work, but all that work went into the back half of the car. The back half of the car then in turn did some work on the front half of the car. This tells us that when I push on the back of the car, the car compresses a little, creating a force between the front half and back half that's half the size of the force I'm pushing with (since half the work done on the back half goes into the front half, giving those two halves the same change in speed). This is really true. If you slice your car in half, then hold the two halves together with some slices of white bread, when I start pushing on the back of the car the white bread will get crushed. Thus, the internal stresses in a car are different for front-wheel-drive and rear-wheel-drive vehicles.
Net Work on the Car
Let's take our system to be the entire car as it drives.
The car might be going at $45 \textrm{mph}$ or $20$ meters/second. In that case, in one second the car travels $20 \textrm{m}$. If, in one second, the car goes from $20 \textrm{m}/\textrm{s}$ to $21 \textrm{m}/\textrm{s}$, and the car has a mass of $1000 kg$, then the change in the car's kinetic energy works out to $20,500 \textrm{J}$. Assuming this is work done by an external force (me pushing, for example, although it's unlikely!) the work done on the car is $20,500 \textrm{J}$.
No-Slip Tires
The above analysis is wrong - the assumption that work is done by an external force is incorrect. The car is accelerating, so there must be an external force on it. But it turns out that external force does no work.
The external force on the car is the force from the road on the tires. Because the tires are not moving with respect to the road, this force does not do work. Thus, the road does no work on the car. This is as it should be. Everyone knows the road is not making your car go. The road cannot do work on your car because the road has no energy to give up.
Similarly, there is a force equal and opposite from your tires to the road, but again this force does no work. This says that your car does not put any energy into the road. This allows a car engine to be more efficient than a jet engine. A jet engine works by pushing air backwards. This air is moving with respect to the jet, and so the jet does considerable work on the air. That means that lots of the energy used by the jet engine goes into the air, and is wasted from the viewpoint of making the jet go.
When I'm pushing the car, my feet don't move while in contact with the road, so again no work is done on us. In both the case of me pushing (as long as I'm part of the system) and the car driving, the car's increase in kinetic energy is not due to external work, but to a conversion of chemical energy to kinetic energy completely within the system.
The Engine
Since the engine is inside the car, if the system we consider is the car itself, the engine does no work on the car. A system can't do work on itself, by definition. Instead, the engine spins an axle that spins the tires, adding kinetic energy to the car, but not doing work. This is why it's possible to say the engine does no work, and it is not dependent on whether or not the tires are slipping.
Since the kinetic energy of the car is changing, we might learn something more by redefining the system. If we define two systems, one being the body of the car minus the engine, and the other being the engine, now work is indeed being done.
The engine does work on the car. It does this by spinning an axle. To spin the axle, the engine must exert force on the outside edge of the axle, and since the outside edge of the axle is moving, the engine does work. (As inflector pointed out in his answer, this work is more easily calculated in terms of the torque on the axle as it rotates, but the two descriptions are equivalent). All the energy the car gains comes through the engine, so in this scenario the engine does all the work to accelerate the car.
The car also does work on the engine in this case. The car exerts a force on the engine. This is a structural force that keeps the engine in place inside the car. The car is paying back a portion of the energy it gained when the engine did work on it.
Conclusion
Two different people (in the same reference frame) can observe the same events, but disagree on whether work is done during them, or on how much work is done. This is because work is a transfer of energy between systems, so that if the two people define their systems differently, they will calculate different values for work done (and for heat exchange).
In light of this ambiguity, it is correct, although incomplete, to state that the engine does no work. This is not dependent on the no-slip tires, and is an artifact of defining systems such that the engine and car are part of the same system.
No slip tires imply that the road does no work on the car, and that the car does no work on the road.
Best Answer
If the question is, "what work does the frictional force of the road do on the car?", then your original interpretation is correct. The road exerts a forward force on the car. This, combined with other forces acting (externally) on the car results in forward displacement of its center of mass, which counts as work.
The way you can show what you want to show is to first write the force balance equation on the car (including only external forces), and then dot the force balance with the instantaneous velocity vector of the center of mass of the car. This accounts for the translational kinetic energy of the car and will give you your work-energy equation immediately.