Playing "outside" can be about throwing in chromatic lines, but there are a lot of ways to get there.
First of all, you say you understand:
the major, minor, harmonic minor and lydian scales,
But this leads me to think you are missing a big part of the picture. Lydian is a mode of the major scale. It's the major scale starting on the fourth. And of course, you can do that from any note (the major scale is also called the ionian mode, followed by dorian, phrygian, lydian, mixolydian, aeolian, and locrian). So if you're playing in a minor key, using the phrygian mode (with it's flated 2nd and sixth) will sound a bit more outside than dorian or aeolian. But you can go further than that. You can do the same thing with the harmonic minor scale. There are different names for these modes (Locrian sharp 6, Harmonic Major, Spanish Phrygian, Double Harmonic Major, Lydian flat 3, Diminished is one group of names, but there are other names for them), and they will pretty much always sound more outside than the modes of the major keys.
At least as useful, if not more so, would be the constant structure scales. There are two, whole tone scales, and whole-half scales. they are just what they sound like - nothing but whole tones, and alternating whole and half tones. An odd thing about these scales - there are only two of each. Odd, huh? Usually just useful for an dissonant run now and then, but they sure do sound outside.
Once you have all of that down, you can start to have some real fun by making up your own scales, and then figure out all the modes for your own scale creations. But really, that's just theory stuff, and when you get on stage you really don't want to think about this stuff, so I tend to think it's better not to worry about getting all that deep. Harmonic minor modes and whole tone and whole half scales are pretty cool, though.
In another thread I suggested Mick Goodrick's
The Advancing Guitarist. There is a lot of stuff in there that will help you with this stuff. Once again, I highly recommend it.
Light
"Cowards can never be moral."
M.K. Gandhi