I agree with you about Cantor's diagonalization. I think that really gives a "tactile" conception of infinity. If I had to explain infinity I'd probably choose to explain injections, surjections, and bijections; followed by countability and uncountability.
If the child is old enough to understand basic addition and multiplication, you can probably run through a short explanation of the different (elementary) number systems.
The cool thing is that you can introduce these concepts (bijections, etc) without calling them by their overly formal names, and yet maintaining rigor.
E.g.: on a pasture, there are black and white sheep. How can you know, without counting, whether there are more black sheep than white sheep, the other way around, or there's the same number?
Well, start taking them out in pairs, black and white sheep in each pair. If at some point you have a black sheep, but no white one to pair with, you know there at least as many black sheep as there are white ones. Same for the other way around. And if all sheep can come out in pairs like that, you conclude there must be the same number of them!
My wording is not the clearest here, but you can get the idea. The notion of "same size" for sets via putting things side-by-side is something kids can get before they learn numbers.
If the child is old enough to understand basic addition and multiplication, you can probably run through a short explanation of the different (elementary) number systems.