Air gives an unmistakable springy feeling and you won't get a firm pedal with air. I would try adjusting the shoes so that they are right on the drums and try the pedal. If that doesn't make the difference than there is a problem with the adjustment of the master cylinder.
