Why is work a scalar quantity? If the displacement is in the direction of the force, then work is positive.
If the displacement is in the opposite direction of the force, then work is negative.
If the displacement is perpendicular to the direction of the force then work is zero.
So, the work done depends on direction. So work should be a vector quantity. Then how is work a scalar quantity?
 A: From a mathematical point of view (ignoring integrals for now), we know that the work is defined to be
$$W = \vec{F}\cdot \vec{x}$$
By definition, the dot product of two vectors is a scalar. So that should be enough to convince you mathematically. 
From a more intuitive point of view, remember that scalars can be negative or positive - this alone does not mean they are defining a direction. As you stated (correctly), the work does depend on the direction of the force. But this does not mean it is a vector itself (just look at the dot product above to convince yourself). Try to think of the force and displacement as more of a cause and effect type of a relationship though. You seem to be implying in your question that these entities are completely separate. If you push on an object in a certain direction, it is going to accelerate in that direction, unless some frictional force balances your push, so the net force is actually 0...then it will not accelerate at all. 

If the displacement is perpendicular to the direction of the force then work is zero.

If there is zero work, then will be no displacement (assuming 0 initial velocity). This is not because there is inherently no displacement...it is rather that there is no net force. Again, imagine pushing on a block downwards, so it does not move at all. This is because the normal force is pushing back at you, so there is no net force on the object at all. That is in fact why it does not move. 
So depending on what direction you push on an object (and subsequently accelerates), you can define work to be positive or negative. This depends on your choice of coordinate system. But to reiterate - work will only be positive or negative. It will never have a direction associated with it. 
A: When we say "work done does not depend on direction" we only mean the direction in which we measure --that is the orientation of our co-ordinate system. We definitely do not mean the relative direction between the force and the displacement.
For a quantity to be a scalar, we should have a fixed value for it which does not depend on the direction of our co-ordinate system. A vector does not fulfil this criterion. For example, if you were to rotate your co-odinate system then the Force vector's components will change and so will the displacement vector's components (the vectors of course remain same just our components change). But their inner product will still remain the same. This inner product is defined to be the work done by the force.
Now, physically speaking why should we expect work to be a scalar? This is a deeper question. Work done on a system changes the energy of that system. And energy should be an invariant quantity that does not depend upon how different observes orient their co-ordinate systems. Because if it does then we will have to prefer one orientation of a co-ordinate system over other and we simply don't see this to be the case in our universe. Therefore, the amount of work done by a force as measured by different observers is also defined in such a way.
A: No, work is definitely not a vector quantity.
A scalar remains invariant under all rotational transformation.
And since  work is a scalar product, it is invariant under any rotational transformation.
It is thus not vector.
A: You might have some other perspective thinking that a scalar quantity is not that, that does not depend on directions of vector quantities, no matter which vectors. 
Every scalar quantity which is the result of an inner product of two vector quantities depends on those vectors, so on their direction, off course. But its still a scalar quantity that does not have a direction...
What makes a quantity scalar or vector in physics is its 'nature' by definition (this is to say that quantities are, a priori scalars or vectors. The algebra comes after... then we realize the necessity of a product that takes 2 vectors into 1 scalar).
This is a good reason why the inner product is so important and not just the outer product. 
