Com qual carro pretende fazer esta viagem?
Não sei te indicar uma empresa que faça este serviço, porem se pensas em alugar um carro e viajar por asfalto, existe uma rodovia a BR 101 que passa por quase todo o litoral brasileiro.
Você pode consultar os mapas rodoviarios do Brasil, e montar seu itinerario, no site do DNIT(orgão responsavel pelas estradas) o endereço é http://www1.dnit.gov.br/rodovias/mapas/index.htm
Abraços,
Marcus.