Fredo was a dead man the moment that Michael realized he betrayed him (at the Superman show). Only question: when?

As Cristina notes, of course the kiss of death would warn Fredo off, when in fact Michael wanted him to return to America, if only so Michael could pump him for info on the extent of the betrayal. Why did he kiss him? Dramatic license: it made for far more drama than, say, the two of them casually sashaying out of the palace and onto the plane.
Yes, Michael waited until their mother died. But Fredo's fate was sealed in Havana. Michael made the "You're nothing to me now" speech only when he was satisfied that Fredo'd told him everything, and had nothing more to give.