Well,
there is a correlation between the energy density a radioactive material has and its decay rate: The higher the decay rate, the higher the energy density.
To store store it for some thousand years, it needs a half life of the same order of magnitude or larger. Also, α radioactivity has typically more energy per decay than other types of radioactivity. So you need an α radioactive material with a half life of several thousand years. Besides Plutonium you can choose some other transuranium isotopes (of Americium, Curium, Berkelium or Californium) or you can use pure Radium. There are also interesting isotopes of Lead and Bismuth available.
An exotic alternative constitutes the isotope 250Cm that decays by spontaneous fission, emitting even more energy than a typical α emitter, and that has a half life in the right order of magnitude.
You can find isotope data on the German language wikipedia here: Liste der Isotope/7. Periode.
EDIT: Handle with care! Some of the suggested isotopes are able to sustain a nuclear chain reaction and careless handling may cause a criticality accident.