I've been studying with Steve for about three years, and along the way I've discovered a few things about how to study rhythm in a flexible way.
You don't need to study a percussion instrument; although it would not hurt, you have enough with your four limbs and your voice to produce rhythm.
The youtube link you posted is a good example. What you want to do is practice spontaneity and flexibility. Steve always stresses the importance of getting things the first time - if you want to get something the first time, you have to start with things that are on your level of difficulty or a little bit above. If it's too complicated for you, you're going to have to work it out. It's ok to work out some things, but you don't want to get into a habit of having to figure everything out before you play it; it has to come straight from your mind to your instrument.
In order to learn how to do two rhythms at a time, you can start by noticing when one rhythm shifts around the beat. Here's what I mean. If you take any rhythm that doesn't resolve on the beat (some people call these rhythms odd) you will notice that if your beat is subdivided by two, you will start your rhythm once on the beat and once in the air, on the upbeat. If your beat is subdivided by three, it will start once on the beat, once right after, and once right before.
Here's an example :
Take this rhythm. Long, short, short.
[ X _ _ X _ X _ ] (a X equals a stroke, a _ equals a rest and  show a beginning and and end for the cycle. The spaces are irrelevant.)
If you play this rhythm against a duple (subdivided by 2) beat, it will look like this :
[ X _ _ X _ X _ X _ _ X _ X _ ] (LSS rhythm)
[ X _ X _ X _ X _ X _ X _ X _ ] (duple beat)
Doing this, you can notice that the first time the LSS rhythm happens, the second and third strokes, SS are subsequent to the beat. The second time the LSS rhythm happens, the second and third strokes SS hook up with the beat (happen at the same time). These are called landmarks; they're very important because they will help you keep your place and feel wether you're right or wrong.
Notice that against a duple beat, the LSS rhythm happens twice before resolving.
Now do the same thing with a triple beat (subdivided by three).
The basic SSL rhythm remains the same : [ X _ _ X _ X _ ]
[ X _ _ X _ X _ X _ _ X _ X _ X _ _ X _ X _ ]
[ X _ _ X _ _ X _ _ X _ _ X _ _ X _ _ X _ _ ]
(sorry, with this forum font the alignment of the rhythms is not perfect).
Notice that the way the rhythms hook up is different this way; first of all, the LSS walk forward on the beat : the first time the stroke is ON the beat, then it's on the second part of the beat, then on the third part of the beat. I call this walking forward, because it keeps creeping forward until it finally reaches the next beat.
Also, check out the way the strokes of the LSS hook up with the beat :
The first LS are with the beat. Then the last S and the first L of the next LSS surround the beat; right before and right after. Then the next S is right after the beat and then the last S resolves on the beat. The last LSS succession is never on the beat; the L is right before and the two SS surround another beat. Very small details like that helped me understand a little of the weights that these rhythms are made of.
Then, when you are comfortable at feeling rhythms shift against the beat, you can play two rhythms against each other. Here again, flexibility is the key: you want to keep creative and just keep making up rhythms. Don't spend too much time on one rhythm; if you can't do it, just pass on to the next one, and keep switching up rhythms like that, to keep your mind young and stay used to intaking new material.
Let's say you take a rhythm that goes like that :
[ X X _ X _ X ]
You have a basic two ways to see this rhythm (there's more to it, but I've never really looked into bigger subdivisions of the beat than 1,2,3,4) :
Duple beat and triple beat. This rhythm doesn't shift against any of these subdivisions, so it's pretty convenient. Try feeling it with a duple beat :
[ X X _ X _ X ]
[ X _ X _ X _ ]
and with a triple beat :
[ X X _ X _ X ]
[ X _ _ X _ _ ]
Once you feel this, try now mixing the LSS rhythm with this rhythm, which I call the trot rhythm. (Feels like a trot to me).
So I'm going to write the beginning of it :
[ X X _ X _ X X X _ X _ X ] (trot)
[ X _ _ X _ X _ X _ _ X _ X _ ] (LSS), etc...
Now remember, you can feel this whole thing against a duple beat, a triple beat, or just a single beat for every subdivision of the beat ! Try all options, and see where you're more strong and weak, everybody has natural strong and weak points.
I don't want to write the whole thing down because that's not the point; just try to notice on your own where do the rhythms start and fall and where are the landmarks where you can feel strongly where you are.
This is just one example, you can make your own based of any rhythms you hear around you or in your mind.
So this is what I practice, and I can feel the results it had on me; I used not to be able to do these at all and now I can do some stuff the first time. After a while your brain kind of gets used to it, it's just a matter of repetition, even though it might seem daunting at first. I come from Switzerland and I didn't grow up around a lot of rhythm, so if I can do some of this stuff that means anybody can !
Hope this helps, let me know if you have any more questions.