TAM, Gol, and Avianca Brasil (still operating separately from Avianca International) fly from GRU and GIG to FOR and REC. Yes, it's obviously physically possible to connect to all of the airports you mention, but you're talking about availability using Amex or Avios miles, and you obviously need to ask them. I've not used miles of U.S. programs for flights within Brazil, but have used AA miles to book a flight from Brazil on Gol and then AA to the U.S. One problem I ran into trying to use UA miles flying TAM and then UA was TAM not releasing seats for booking with miles more than 90 days in advance. Makes advance reservations tough. You need to ask Amex and Avios.

By the way, if you have to pay for your own flights, check the sights of individual airlines above (also Azul, which flies to/from Campinas, not GRU). We're flying FOR-GRU next week, and Avianca Brasil was less than half the cost of TAM or Gol.