It's really quite simple.
Your host would merely have to set up visitnatalbrazil.com as a new site and initially point it to the same folder as
www.visitnatalbrazil.com .
When they've done that, they need to visit the Properties of the visitnatalbrazil.com site, and click the Home Directory tab. There's an option there to redirect to a URL, which they would pick and type in
http://www.visitnatalbrazil.com and check the "A permanent redirection for this resource" box.
That's it.
They can charge you for anything they want, and since this is non-standard they might. I can't say for sure, although it's about a two-minute job in IIS.