I think there are a few reasons for this, drawing from both the movies and the books.
Firstly, Clemenza was known to be an extremely good caporegime and mentor. A quick check on the Godfather wikipedia points out that FIVE future capos were started in his regime - Sonny, Lampone, Pentangeli, Ritchie Nobilio and Joey Zasa. This shows that he has the ability to spot and nurture the talent needed to start a family.
Furthermore, in the scene when Michael asks Tessio and Clemenza to be patient and trust him now that Vito is turning all responsibilities over to him, Clemenza is the one who asks Vito Corleone for permission for he and Tessio to start their own family, strongly suggesting that while neither of them believed Michael was an appropriate choice for don, he was the one prepared to speak out about it. Another fact is that in the books Clemenza is frequently shown to be quite brutal in his dealings (whereas in the film, although brutal, he is also given an almost jovial "big-guy" character).
However, whilst Tom took all this as being evidence that Clemenza would be more likely to rat Michael out and betray the family, Michael recognised it as loyalty and dedication to Corleone family (coupled with a lack of intelligence to look for opportunities elsewhere, beyond his own family). Tessio on the other hand masks his emotions throughout the entire don-changeover-process and Michael knew he had the intelligence, cunning and ability to betray the family, which is what led him to suspect Tessio.
Finally, if at all interested, Clemenza was meant to return in Godfather II, but the actor, Richard Castellano asked for too much money (he was actually the highest paid actor in the first film!). I've also heard he demanded control over all his lines, although I've not found a source to substantiate that. That's why he never returned.
In the books, he got his own family and even acted as a consigliere at one point (albeit in a rather temporary capacity) for Michael. He died of a heart attack whilst cooking dinner, although it is frequently alluded to that he may have been assassinated by the Rosato Brothers.