I have a distinct memory of my second grade teacher handing out a logic grid puzzle to the class one day near the end of the year. I remember thinking, "This is fun, but what does it have to do with math?"
Of course, logical puzzle-solving is an important kind of math, and should be explicitly included in the curriculum. Students of all ages should be taught about logic grid puzzles, tangrams, mazes, magic squares, sodoku, minesweeper, Rubik's cubes, towers of Hanoi and so forth in math class, as well as games such as nim, dots and boxes, sprouts, etc. Puzzle-solving is a basic mode of creative thought, and it needs to be explicitly included in the curriculum.
In addition to such explicit logic puzzles, teachers at the elementary school level should endeavor to include small mathematical puzzles that the students can potentially solve. Especially if they work in groups of two or three, fourth or fifth grade students ought to be able to solve a simple puzzle like
Find two numbers whose sum is 22 and whose product is 96.
We teach explicit methods for these things when they get to algebra class, but in elementary school students ought to be clever enough to figure out a puzzle like this without having any explicit method. Other puzzles like this include
How many different ways are there to make 36 cents in change? (I'm assuming U.S. currency.)
or
A solid, four-inch cube of wood is coated with blue paint on all six sides.
Then the cube is cut into smaller one-inch cubes.
These new one-inch cubes will have either three blue sides, two blue sides, one blue side, or no blue sides. How many of each will there be?
A general rule for such puzzles is that the children should not be solving them using some method or algorithm that they were explicitly taught. Math is not a rote subject, and puzzles like these are much more representative of real mathematics than multiplying three-digit numbers or reducing fractions to lowest terms.
Finally, in addition to puzzles, there are many possible geometry-based toys that children can use creatively, including polydrons, zomes, tangrams, and so forth. These could lead to all sorts of interesting classroom activities -- e.g. a contest to see which group can construct the most interesting closed shape (polyhedron) using polydrons.