I'm not an expert on Northeastern Brazil as I haven't been to many places there, but I'd agree with maracatu on the places to visit around Salvador (Abrolhos and Morro de Sao Paulo seem to be amazing, especially if you dive or snrokel). Porto Seguro is almost half the way, so you could try a bus from Salvador to there, and then fly to Vitoria or Rio (at least 5-7 days here). I don't know the coast of Espirito Santo. I heard it's nice, not sure if it's worth the stop though...
Then from Rio to Sao Paulo. I personally don't like Sao Paulo city very much, but it's culturally rich and full of city things to do. The coast has a couple of interesting beaches, I would say Ilha Bela or Ubatuba. Check this link for seeing the main ones. http://www.loucosporpraia.com.br/praias-lindas/praias-lindas-sp/
Depending on how much time you'll have to visit the south, there's an island in the coast of Parana called Ilha do Mel, you can get there from Pontal do Parana or Paranagua (you get there by bus from Curitiba). I'm a suspect as I spent my childhood frequenting the island, but it's paradise to me and definetly worth the visit for 3-4 days at least. It's a different atmosphere from the rest. The nearest big city is my hometown Curitiba - which is also a beautiful city for a 1-2 days stop if u want to see some nice architecture, many parks, green city.
From there, you can either flight to Foz do Iguassu to see the Iguazu falls, which are amazing but totally out of your route - and then from there to Florianopolis - or a bus from Curitiba straight to Florianopolis (or flight from SP if you decide to skip Parana) and another 5+ days there. There are many beautiful beaches in the State of Santa Catarina, you can try at least 2-3 days in another beach southern from Florianopolis - I'd recommend Guarda do Embau, Praia do Rosa, Farol de Santa Marta.... It's a completely different atmosphere from northeast and Rio - definetly worth it.
Also, from the timeline, you're probably spending Carnival somewhere around the south (17th february). Be aware that most of hotels/pousadas offer packages of at least 4 days (saturday to tuesday) and prices go significantly higher as Carnival approaches. Try to avoid the road on the 13th, 14th, 17th, 18th and 22nd of february. As you'll be on vacation, you can spare yourself from having a 10-15 hours drive when it usually would take you 5h or less...
Try to plan your Carnival the sooner you can if you want to do something nice on these days ;) most of the coast will be crowded and best packages sell out soon.
I'd definetly skip Rio Grande do Sul. Apart from a cozy german city called Gramado up in the mountain, there's not much to see... Porto Alegre is boring in my point of view, although is the best airport to flight to Montevideo..
I wouldn't rent a car as most said, so combining flights for longer distances and bus for distances up to 500km (or 700km - no more) is the best option.
Most of cities referred here are beaches. So if you have any other interests than that, let us know!
Good luck on your planning!