For spheres, balloons would work well. Everyone could have a balloon and a marker and draw their own triangulations. You can imagine the awesome squeaking noise.
An advantage of this would be that people could try to draw really funky triangulations to test if the Euler characteristic actually worked. I feel starting with spheres (ie balloons) and trying lots of different triangulations would really convince people that it really works. Only then is it really worthwhile to try other shapes, in my opinion.
As to the other shapes, play-dough is a possibility, but it's probably a bit too floppy for the purpose. Taking someone else's answer, you could use real dough baked into bread of various shapes, but of course not easy to give one to every student.
Instead of making them smooth, you could make them out of cubes glued together. Cubes don't take too much effort to make out of paper and tape and with enough of them the students could all make their own, triangulate them and group them based on their characteristic.
This has an advantage that you could actually start with a single cube and show it comes to the same characteristic as the sphere. Also, students could easily do it at home if you gave them a cube net they could print. Making it possible for students to investigate by themselves is always a good thing. (This is one reason why I prefer not to use commercially-produced products but things you can find in your home.)