Without losing the one I have.

If I get a new one and tell the old one to leave me, what happens to him? Can I ever get him again?

No and Yes, you can rehire a previous companion. In the vanilla game, you can have one human and one non-human at a time. When fired, they return to where you found them. If you're on PC, there's an Unlimited Companions mod and you can have them all. More than 3 is a lot to handle though...it's just about right. I like having Boone, Arcade and ED-E with me.

I read something about putting them in my room in the casino, is that possible?

Also, do they have levels? If I'm lvl 20 and I have boone, and I go get veronica - is she going to be weak?

I never use that room but I have read that you can send them there. They are still your companion though. They'll just wait there for you.

And, as long as your Charisma is high enough, I can't imagine any companion being weak. Charisma affects Companion Nerve from +5 at CHA1 to +50 at CHA10. They deal out more damage the higher it is.

Veronica is a great companion...she's very tough. She's Melee though and runs up to everything so if you stand back and shoot, she'll probably be in your way. Boone is a sniper so shoots from far away. ED-E does that also. I'd say Raul and Arcade are more mid-range. Rex is a dog so he has to run up to attack. Cass likes shotguns so that's a close mid-range. Lily is melee with a huge weapon she hit me with once. Did I miss anyone? Also, I give my companions better armor and weapons and keep them supplied with ammo so they are strong. Hope that helps.

You CAN send them ALL to the Lucky 38 without any problems.

Now the stupid question.

How do I send them there?

There's an option in the text http://fallout.wikia.com/wiki/Fallout:_New_Vegas_companions

The Lucky 38 speech option should appear after you've spoken with Mr. House and he comps you the Presidential Suite.

There is a glitch somewhere to get more than one companion on console... And Companions arnt weak no matter what, really. Im mean, not being able to die really does make them gods.

If you want to change a companion just tell them you have to go on without them, you ahve to part ways etc and they go home. They go back to were you found them. Or send them to the suite in the Lucky 38 once you talk to Mr House and he gives you the presidential suite.

well you CAN'T HAVE ONE! get BACK in the hole! back! :yucky:

There's a mod that lets you have as many tag alongs as you want depending on your charisma.