A typical launch carries a 3-5% excess fuel load for safety margin, so there was always some extra fuel aboard at separation. The big factor that changed the game was that the Merlin 1-D engine was suppposed to reach 120,000 lbs of thrust each, but instead is testing at 145,000 lbs of thrust with a higher ISP, which IIRC is about 310 seconds, which is phenomenal for a Kerosene/LOX engine.
With the extra thrust and the better performance, it meant that they could either expand the payload by a few thousand kilos, which would still be an option with a more expensive, expendable flight, or they could have 6-8% fuel reserves at the end of the stage separation.
Without the payload to push, that 6-8% is more than enough to slow down a very light "empty tin can" and get it out of it's sub-orbital trajectory. If you watch the video, they're only burning three engines to deorbit, and one engine to land the first stage. The claim is that the first stage actually has the thrust to return it to the launch site, which might be possible. First stage separation is only a few hundred miles downrange, and you could actually just slow down and let the Earth rotate under you to move back west. In any case, you'd want to bring the speed down to where you are basically in a straight line free-fall back to the launch site, using only maneuvering jets for stability until a few miles above the ground, when you light the center engine and tail land it.
Clearly this isn't something simple, either. They aren't going to be flying this by next week or anything, and the actual fact is that they are likely to be unable to recover some of these first and second stages to bad or uncontrolled landings -- which is exactly the same as what happens now, so this can only be a win scenario for them if they get it working. I'd love to see $10/lb to LEO pricing.
As for the use of parachutes, the first launch of Falcon 9 attempted to parachute the first stage back to the ocean, but from what I heard, the aerodynamic forces on the tumbling, uncontrolled reentry of the stage caused it to break up before the parachutes were deployed. The second stage reentry is under even higher stresses, and I don't think they even tried to recover it before the grasshopper program.