The song is by Ian Davison, who's singing in the Youtube clip linked to above. The lyrics quoted are definitely from Ian's song.

Ian has made so many wonderful songs that it would be a trivial gesture to list them. So here's just one a link to Ian's MySpace recording of "Mandela Danced"

Mandela Danced

"We'd sung about him for years,
And there were speeches everywhere.
But I'll never forget the cheers,
When Mandela danced in the Square."