The Portuguese would have landed in Brazil. (For a POD, Columbus fleet is sunk by a hurricane/storm.) The fastest way for a sailing to get from Portugal to the Tip of Africa is to travel west on the trade winds until the ship crosses the equator, then take the trade winds east back to Africa. This faster path takes a ship far from the Africa Coast, and it was just a mater of time til a Portuguese ship bumped into Brazil.
http://www.enchantedlearning.com/explorers/samerica.shtml See below for text.
CABRAL, PEDRO ALVARES
Pedro Álvares Cabral (1467-1520) was a Portuguese nobleman, explorer, and navigator who discovered Brazil on April 22,1500. His patron was King Manuel I of Portugal, who sent him on an expedition to India. Cabral's 13 ships left on March 9, 1500, following the route of Vasco da Gama. On April 22,1500, he sighted land (Brazil), claiming it for Portugal and naming it the "Island of the True Cross." King Manuel later renamed this land Holy Cross; it was later renamed Brazil, after a kind of dyewood found there, called pau-brasil. Cabral stayed in Brazil for 10 days and then continued on his way to India, in a trip fraught with shipwrecks (at the Cape of Good Hope), and fighting (with Muslim traders in India). After trading for spices in India, Cabral returned to Portugal on June 23, 1501, with only four of the original 13 ships. After this journey, King Manuel appointed Vasco da Gama to head the next expedition, and Cabral retired.