Does work done depend on the frame of reference? Suppose I am sitting on a bench and looking at a moving car. Force is applied on the car by its engine, and it makes it displace, hence some work is done on the car. But what if I am sitting in the car and looking at the bench? The bench covers some displacement, but who has applied force to it? Is any work done on it?
 A: It's a good question. You're right that the bench has kinetic energy in the car-frame, so it seems natural that somebody had to do work on it.
That's not true, however. The energy of an object can be completely different depending on what reference frame you look at it from. So can the work. But in this case, the work on the bench is 0 no matter how you look at it, because the force is zero. So even if there is a displacement,
$$W=0\cdot d=0.$$
In an inertial frame (one not accelerating), you only require work to change the energy of an object. In the car's frame, the bench has some kinetic energy, but it always had that kinetic energy. So nobody had to apply work to it.
A: 
The bench covers some displacement but who has applied force to it. Is some work done on it?

No.
Work is the change in kinetic energy. In the simple case, we can think of it as the change in velocity. The velocity of the bench didn't change in your example, so there's no work.
But let's say it does change; let's modify the original question so the car is speeding up. To someone in the car, it looks like the bench is speeding up in the opposite direction. So now we do have a change in velocity, and thus a change in energy, and thus work.
So who did the work in this case? The car engine. You might ask "well how did the engine do work on the bench, it's not even touching it!". Well who said that the item doing work had to be in any way related to the object you're measuring?
For instance, what if the bench is on a treadmill and the treadmill starts moving? You would still say work was done on the bench, even though the motor was connected to the belt. You're OK with that?
Ok, well in this case, the car's engine spins the planet in the reverse direction, and the bench is on the planet. It's the exact same setup.
Now you'll likely say "there's no way that the car engine is spinning the whole planet!" - but that's precisely what Galilean relativity is all about. If you say "I'm sitting still in this car", then yes, by definition, the planet is spinning the other way.
You may not feel comfortable with that statement, but physically it's up to you to pick the reference frame that "makes the most sense". If that statement doesn't make sense, then simple pick the Earth as the reference frame - now it's the car that's speeding up and you're back to the bench not moving.
There's zero physical difference in any of these, it's all nothing more than what frame you feel most comfortable with? Did the car accelerate one way, or the Earth the other? You decide, it makes no difference in the end.
A: Does work done depend on the frame of reference?
Unequivocally, YES. Forces are the same in any inertial reference frame, but displacements are not.
You are getting confusing and confused answers because the wording of the question is not entirely clear.  There seem to be two possible interpretations, neither of which effectively gets at the heart of the title question: (1) the car is accelerating, or (2) it is moving at a constant speed.  If (1) then the car frame of reference is non-inertial, which adds unnecessary complication if what you really want to know is the answer to the title question.  If (2) then there is no net force on the car, and hence no work done in either frame.
So, forget the car, accelerating or not, and consider instead a man lifting a heavy bag vertically at constant speed while riding an elevator that is itself rising at a constant speed.  The force applied by the man to the bag, in any frame, is just the weight of the bag.  The distance over which that force is applied depends on the reference frame: in the elevator frame, the man moves the bag from knee to shoulder height in a certain period of time--say a one meter displacement over the course of five seconds.  In the earth frame, the elevator might have risen two floors (six meters) during those same five seconds, so the total displacement of the bag is seven meters, and the work done on the bag is seven times greater than in the elevator frame. Meanwhile in the bag frame, the displacement, and therefore the work, is zero.  
A: In a friction free world, the car moving with a certain velocity will not have any forces acting on it. If there were forces acting on the car, it would be accelerating.
There can be multiple forces acting on a body, so it's really important to specify which force are we talking about when we are calculating the work. 
$\mathcal{Case (i) - }$ 
When you are sitting on a bench, you will observe the car to be accelerating from your non-inertial frame of reference (frame at rest or moving with constant velocity). Since, the car is accelerating, there must be some force acting on it.  Therefore, that force will do some work. 
$\mathcal{Case (ii)-}$ 
Now when you are sitting in the accelerating car, an inertial frame, there will be pseudo force acting on all the objects you observe from your frame of reference. That pseudo force will certainly do work on the bench.
Although the engine will not doing any work on the bench.
A: Let me address your scenario first. What you suggested is bad physics because it breaks the conservation of energy. It doesn't work because the car is not an inertial frame. An inertial frame is arguably defined as one in which newton's laws work. We know that the bench frame is inertial because momentum is conserved as the car accelerates. The car frame is not inertial so it is meaningless to apply newton's laws and subsequently, energy conservation (unless you introduce fictitious forces, but those are limited to only a few scenarios). If this makes the definitions and statements in newton's laws seem circular, it's because they are. They empirically work relative to the fixed stars, (and any galilean shift of that) and one can show that they are true for frames purely accelerating due to gravity, as in the earth, so they are very useful anyway.
Now to answer the question you literally asked. Momentum change of a particle is conserved between inertial reference frames. However, energy change of that particle across a chosen path is not preserved, once you apply the appropriate transformations. The work done on a closed system however, is zero in any inertial reference frame, this is the conservation of energy and it is all that is needed to allow the frames to agree with each other.
For instance, think of an elastic collision between two particles with equal and opposite velocities magnitude $v$, in frame A, the work done on each particle is $mv^2$. Now choose a frame with a particle at rest, the work done is now $2mv^2$, the energy change of the system in both frames is 0.
A: Wikipedia says

In physics, work is the product of force and displacement.

Or to put it mathematically $$\overrightarrow W =\int_{\overrightarrow x_{i}} ^{\overrightarrow x_{f}}\overrightarrow F\cdot \overrightarrow {ds}$$ here ${\overrightarrow x_{i}}$ and ${\overrightarrow x_{f}}$ are initial and final position vectors and that dot is dot product.
As both $\overrightarrow F$ and $\overrightarrow {ds}$ are both frame dependent thus their product will change with frame transformation(unless there is some specific reason). It really depends on the context.

The bench covers some displacement but who has applied force to it. Is some work done on it?

Note that you are observing bench in a non inertial frame so you have to take into account pseudo forces which seem to do negative work on the bench on your system and decrease its energy(in that frame). 
So, yes work is frame variant, it has to be, as follows from it's definition. 
A: If your velocity is zero then due to work energy theorem the work done would be zero. But if you are accelerating then pseudo force would do the work
A: If the frame of reference is on the  accelerating car, we have a non inertial frame of reference, so a pseudoforce (~fictious force) is born on the bench, which makes it accelerates as to the non inertial frame of reference.
