1. AINAL, so I might say legal matters wrong for not understanding completely how the tax law works in Brazil, (Tho I do like to search about it), but I might find someone who could help you guys with it.
2. Currently, there is a law already approved (now being regulated with complementary acts) about how taxes will change in Brazil to the VAT model, this could increase/decrease taxes for a service like yours.
Besides these 2 points, we could talk via email (xunjin.coder@gmail.com) to might find a way like AWS did, creating a Brazilian subsidiary, to be able to generate NF-e in accordance for each valid Brazilian Tax Registration Number (CPF/CNPJ) and issue the invoices in BRL.
This page https://aws.amazon.com/legal/aws-sbl/ could have more info to elucidate how AWS does.