It's always installed with Leopard, you must have deleted it youself, so if you have TimeMachine on you can retrieve it from there. You can also use
Pacifist to retrieve it from the Leopard DVD.
Video chat with what? For AIM I believe iChat is the only solution. Yahoo Messenger does webcam video, but no sound, and for MSN there is some ugly third party app available as well. All of those will kick you out of Adium though. You can log into one account only with one client at a time.
Well, Skype wouldn't kick you out of Adium since it's not supported by the latter.