You don't need nuclear waste to be stored for millions of years, after a hundred or so anything of exceptional danger has decayed and what is left will be such a low level of radiation that common clay bricks are just as much of a risk. The "hotter" a nuclear material is, the faster it decays, and materials that remain radioactive for thousands of years are not especially radioactive.