How is this process not quasi-static yet reversible? Consider a (adiabatic) canister with a piston containing some gas kept in a vacuum. There are two weights on the canister which equalize the pressure of the gas on the piston. Assume the system is at equilibrium. 
I remove one weight from the piston. The system will go out of equilibrium. After some flux, it will again settle into equilibrium. 
Clearly, this is not a quasi-static process. But its a reversible one, isn't it? If I put the weight back on the piston, the system will again achieve its initial state. How can a non-quasi-static process be reversible? 
EDIT: According to Wikipedia, a reversible process "is a process that can be 'reversed' by means of infinitesimal changes in some property of the system without entropy production". So, if a process can be reversed without the means of infinitesimal changes without entropy production. Would that qualify as reversible? (as in the example given above) 
 A: In the process you describe the system won't necessarily return to its original state.
Suppose you instantly remove the weight and lift up the piston so the gas expands irreversibly to it's new equilibrium volume. The gas does no work in expanding so its temperature doesn't change - all that happens is that the pressure falls.
Now compress the gas back to it's original volume reversibly by lowering the weight back on very gradually. Now you are doing work on the gas so its temperature increases. When you eventually release the weight you'll find the gas temperature and volume are different to the initial state.
If you do the cycle reversibly you'll find that the work done by the gas as it expands is the same as the work done on the gas as it's compressed, and it will return to its initial state. However this isn't the case if the expansion/compression is not revesible. This is because work is not a function of state.
A: In the context of equilibrium thermodynamics, when we say that a process is reversible, we usually mean that the process is well-described by a continuous path in thermodynamic state space (namely it is quasi-static) and that the system can be taken along the same path in thermodynamic state space, but in the reverse order.  Since in the example you gave, the system is only in equilibrium in the initial and final states, it doesn't make sense to talk about reversibility.
It's true that the system is going from one equilibrium point (point in thermodynamic state space) to another and then back again, but one cannot speak of the system "retracing" its thermodynamic steps so-to-speak because from the perspective of equilibrium thermodynamics, these intermediate steps are not well-defined macroscopic states.
A: Although this isn't obvious, the system doesn't return to its initial state. If you were to very slowly remove the weight from the piston, then the gas would do work on the piston as you removed it, which means that its internal energy would be reduced. If you remove the weight very quickly then the gas still does work on it, but it will do less work than it would in the reversible case, which means that its internal energy will change by a different amount.
There are several possible reasons why the work can be less. One is discussed in John Rennie's answer --- if you lift the piston so rapidly that the gas molecules can't catch up with it then they will do no work at all. However, a much more realistic scenario is that once you remove the weight, the piston starts to oscillate up and down. After a while the oscillations reduce in amplitude due to frictional dissipation in the gas, and the piston comes to a stop.
In this scenario, under normal everyday conditions, the gas stays at a pretty homogeneous pressure the whole time, meaning that the vacuum effect discussed above isn't very important. Instead what happens is that the gas does work to push the piston up, in pretty much exactly the same way as it would in the non-reversible case. Once the piston gets to the equilibrium position, the gas is in pretty much the same state it reaches in the quasi-static case. The difference is that the piston still has some kinetic energy, which is why it keeps moving upwards and begins to oscillate. Once the oscillations have died down, the kinetic energy that was in the piston is now in the gas, in the form of thermal motion of its molecules. Therefore, once the piston has stopped moving, the gas is at a higher temperature than it would have reached in the quasi-static case.
Once you put the weight back onto the piston, the same thing happens: the gas gets compressed, pretty much reversibly, but the piston still has kinetic energy, so it oscillates. Once the oscillations die down, the gas will have a little bit more thermal energy than it would have done otherwise.
This means that, after removing and replacing the weight, you haven't restored the gas to exactly its initial thermodynamic state. Instead you've heated it up very slightly.
To put some numbers to this, let's assume that the weight you remove has a much smaller mass than that of the piston itself, so that we can assume the pressure is constant. (There's no real need to do this - it would be easy enough to consider changes in pressure due to the ideal gas law - I'd just like to keep it simple.) We'll also assume the volume (and therefore total heat capacity) of the gas is big enough that its temperature stays approximately constant.
So: let's you remove a mass $m$ and the piston starts to oscillate, but eventually comes to rest a distance $\Delta h$ higher than it was before you removed the weight. If you had removed the weight slowly then the gas would have done work equal to $mg\Delta h$ to move the piston, and therefore it would have lost this amount of energy. In reality the gas did do (most of) this work, but it was turned into kinetic energy and then went back into the gas, so its internal energy actually changed by zero. However, replacing the weight does cause a net amount of work to be done in compressing the gas. The oscillations mean that slightly more work than $mg\Delta h$ will be done in the non-quasi-static case. We'd need to do the full ideal gas equation calculation to work out how much, but we know it must be at least $mg\Delta h$. So the total internal energy change after removing and replacing the weight is $\Delta U \ge 0 + mg\Delta h =  mg\Delta h$. So the gas has more energy at the end of the process than it did at the start, as claimed.
You specified that the piston is adiabatic, but we can do a similar analysis in the case of an isothermal situation. In this case the gas does end up in exactly its initial state, but it exports a little bit of energy into the heat bath. If you consider the system and the heat bath together, the final state is slightly different from the initial one, because the heat bath ends up with more energy than it started with.
This is generally what will happen in an irreversible process: the final state of the system and its surroundings will be different than in the irreversible case. Very often, but not always, this difference will be in the form of a slightly higher internal energy. It might not always be obvious, but it will always be there if you analyse the process carefully enough.
Nevertheless, there are plenty of processes that are (practically) thermodynamically reversible while not being quasi-static. A simple example is an ideal frictionless pendulum, which repeatedly converts gravitational potential energy into kinetic energy and back again, always returning to exactly its initial state. Of course, no real pendulum is completely frictionless (just as no real process is completely quasi-static), but you can get pretty close with good engineering.
A: 
If I put the weight back on the piston, the system will again achieve its initial state.

No, it won't.  In the end, the pressure will be the same, but the temperature and therefore the volume will be higher.  
Firstly, in a real system there will be friction due to gas viscosity and piston/cylinder interaction.
But even in an ideal system, after the first weight is removed, the gas expands against only the pressure of the remaining weight(rather than the gas's own higher pressure) and therefore does less work than it otherwise could. $\Delta U_1 = -W_1$.  When the weight is replaced, the compression is against the gas's own pressure, and more work would be required to return the piston to its orginial position than the gas orginially did.  $\Delta U_2$ would need to be of greater magnitude than $\Delta U_1$ to get back to the starting pistion position.
see section 3.3.2 and 3.3.3 of the following reference:
http://sites.tufts.edu/andrewrosen/files/2012/11/Thermo-Review.pdf
A: The process is obviously quasi static if dynamics are ignored and as long as no friction is assumed also reversible. Perhaps the key is to consider what "removing the weight" actually means. If the weight is removed by a vertical action from $h_0$ to $h_1$ (heights, where the indices mean equilibrium positions) and you do it really slowly (dynamic effect by moving masses neglected), the process is quasi static. 
If however the weight is removed quickly or even instantanously (eg. by removing the weight by horizontal action at $h_0$) the system will oscillate stationarily around $h_1$. The energy stored in the oscillation would be the difference between the potential energy $mg(h_1-h_0)$ and isentropic volume change work $\int_0^1 pdV$, where $m$ is the removed mass, $p=p_0(V_0/V)^\kappa$ and $\kappa=c_p/c_v$. While obviously in this situation still everything is reversable, it's also still quasi static with respect to internal of the closed system where no non-equilibrium processes take place, besides some local effects which average out. In other words for any position $h$ of the piston the internal state is given independently of circumstances outside the system.  
A: The other answers showed that the energy of the final system is greater than the energy of the initial system, because you are heating the gas.  Here's another way to see this:
In the first step, you remove the weight at height $h_1$.  In the second step you replace it at a higher height, $h_2$.  In between these steps you need to bring the weight up from $h_1$ to $h_2$, which takes work.  The environment will lose energy in performing this work, so the system must gain energy to compensate.  One might object that you could just even things out in the end by transferring energy back from the system to the environment.  However, the environment lost energy in the form of work, and the system gained energy in the form of heat, so the net energy transfer is irreversible.
A: It is just not a reversible process.
Calculations for the irreversible sequence
Say the piston has an area $A$, the two masses are $m$ and $m'$, and the initial state of the gas is characterized by:
$$V = V_0,$$ $$P = P_0 = P'_e = (m + m') g / A,$$ $$T = T_0.$$
with $P'_e$ the external pressure applied to the piston when both masses $m$ and $m'$ are present.
When the mass $m'$ is removed, the gas, at initial pressure $P_0$ expands against the new external pressure $P_e = m g / A < P_0$, doing a work $W = -P_e \Delta V$ until it reaches the new state: $$V = V_f,$$ $$P = P_f = P_e,$$ $$T = T_f.$$
When the mass $m'$ is repositioned, the gas is compressed by the new external pressure $P_e'$, doing a work $W' = - P_e' \Delta V'$.
At the end of the process, the internal energy of the gas has changed by the amount $$\Delta U = W + W' = - P_e \Delta V - P'_e \Delta V'.$$ So even if $\Delta V'$ were equal to $\Delta V$ the system is not brought back to the same state.
The crucial point here is that during the expansion and compression phases, there is a discontinuity between the internal and external pressure, and therefore an asymmetry between the expansion and the compression. This discontinuity is the reason why it cannot be considered as a quasi-static process. In fact, the term "quasi-static process" is a misnomer because what it designates it is not a process at all but a range of constrained equilibrium states. Giving this range of constrained equilibrium states determines nothing about the various actual possible processes that could navigate the system from one equilibrium state to the next.
Scenario of a reversible sequence (reversible cycle)
For the process to be reversible, the external pressure applied to the piston should always equal the pressure of the gas $P(t) = P_e(t)$ all along the transformation, with for instance $P(t)= n\text{R}T(t)/V(t)$ if it were a perfect gas. Such a process would require to "remove" the mass $m'$ very progressively.
In such a process the work done by the gas would be exactly the opposite during the compression as it was during the expansion, and the gas would then be brought back to its initial state.
Entropy increase
One might then wonder how the entropy has increased during the first irreversible sequence, since $Q = 0$ all along the process which is assumed to be adiabatic... There are two ways to analyze the situation:

*

*The first way is to recognize, as explained in the answer by Nathaniel, that for the system to reach a static equilibrium, there must be friction happening which stabilizes the piston at each new position. If there were no such friction, the piston would keep oscillating after the mass $m'$ had been removed or after it had been repositioned.


*The second way is to be aware that the relation $\text{d}S = \delta Q/T$ only applies to reversible processes. In the irreversible process, the entropy increases due to the pressure discontinuity in the composite system ($P_0 \neq P_e$). To compute the resulting increase in entropy, one would need to find a reversible process that bring the system (and its surrounding) to exactly the same final state, and evaluate $\text{d}S = \delta Q/T$ for the gas along this reversible process. Obviously, such a reversible process would not be adiabatic, but it would be computable.
A: Are you sure the gas is really going out of equilibrium?
Quote from General Physics, by L. D. Landau and others (the link requires login, to "borrow" the book):
The context is the expansion of a gas in a thermally isolated cylindrical vessel with a piston.

Here, "sufficiently slowly" means, therefore, so slowly that the gas
is able to establish thermal equilibrium corresponding to every
instantaneous position of the piston...Analysis shows that the
condition would not be fulfilled only if the rate of movement of the
piston were comparable with the velocity of sound in the gas."

Here's a similar quote from Pippard, where by fluid he means a gas or liquid:

Usually in practice, however, a fluid requires very little time to
equalize its pressure, and the change can be carried out quite quickly
without provoking a significant departure from equilibrium.

