In reply to Rick T:
Not done any climbing there but lived in Brazil for a good while and know there are some routes on the Corcovado (the hill with the big Jesus on top) as I've seen people topping out on the tourist viewing platform there. Must be a pretty cool venue - I'd love to go back and do it!
I think there are also some routes on Pao de Acucar (Sugar Loaf), the hill with the cable cars on it. I've read something about the local mountaineering club meeting there. I think they've got a little wall at the upper cable car station.
Failing that, you could get out of Rio and head for the Sierra dos Orgaos, accessible from either Petropolis or Teresopolis (regular buses from main Rio bus station) in the countryside of Rio state. There are some stunning pinnacles in the range that look like they'd be fun - the 'Dedos de Deus' (God's Fingers).
Petropolis is a beautiful town, used to be the seat of Brazil's royals. There's a great three-day trek from there to Teresopolis through the Sierra dos Orgaos. Sadly didn't finish it myself as I broke an ankle half way through and had to be choppered out.
I've got an OS-type map for Sierra dos Orgaos somewhere. Let me know if you're interested and I'll scan some bits in, mail 'em over to you.
Get out there, Brazil is dirt cheap at the moment. (Something like £1 to five Brazilian Real.) With the exchange rate as it is, you can get an all-you-can-eat meal in a top Brazilian steakhouse for about three quid, a litre bottle of beer for about 50p!
RobE