Possibly a Portuguese explorer like Cabral or Coelho, someone who sails sails far into the Atlantic to catch the trade winds to carry them along the coast of Africa, and then seeing birds or debris that convinces them that they're near land. This would happen in the early decades of the 16th century, so not very long after Columbus.
Probably. I remember vaguely hearing about how sailors knew of what was roughly modern Brazil years before it's official discovery, but nobody really cared to report about it because they didn't think it had any value.