^ What he said-- definitely go for Barcelona!
I think you'd have a very difficult time trying to squeeze in Barca, Madrid *and* Paris. I love Paris, it's wonderful, but you'll definitely get more, uh, bang for your buck in Barcelona.
A ticket from Toulouse isn't going to be too expensive either. Hostels are definitely the way to go, in my opinion... I stayed at the Ideal Youth hostel right on Las Ramblas in Barcelona; other people have recommended the Kabul and a couple of other ones I can't remember at the moment.
You can check out places to stay on the
TravelPunk main page.
Have fun, whatever you do! And welcome to the boards.