Personally, I would add a separate answer (as P.T. did in this case). He provided the up-to-date information and should get credit for it. So far he's got 40 rep from the answer than he wouldn't have gotten by editing the other answer, and I think he deserves it. It also serves to alert the post owner that things have changed, which an edit would not. Finally, the editing page says you should "clarify meaning without changing it". This sort of edit would clearly be changing the meaning.
If the post is CW then an edit is appropriate, of course. For example, Separate answers on our rooting questionour rooting question have been deleted and incorporated into the main post since we want everything to be cohesive.
It's certainly inappropriate to downvote the outdated answer (IMO) since the answer was correct and useful at the time it was posted; it's not the answerer's fault that Google changed the game. I would consider adding a a phrase like "At the time of posting" to the outdated answer, though, just to make it clear that the answer was once correct to anyone unfamiliar with the history of the issue. As Bryan notes you could also mention the newer answer in an edit, but I would be careful with this; you probably don't want to edit another answer to point to your own since it may be viewed unfavorably.
(And "wrong" answers should never be flagged, outdated or not.)