Sort of...
All modern nuclear weapons consist of a primary and a secondary. The primary is triggered using chemical explosives (compression) and an 'initiator' (for an initial burst of neutrons) and has a yield in the low kiloton range.
The energy from the primary is then used to both compress the secondary much more efficiently, and provide the neutrons to initiate the reaction. This secondary can then provide a yield deep into the megaton range.
It is possible to add further stages, and in some (realized) designs, this was done, but for modern weapons this is unnecessary.
Materials
- Plutonium-239: Half-life of about 25 kiloyears. Will alpha-decay into Uranium-235, which, in the amounts that it will appear in, will substitute just fine. You mainly have to worry about the effects of the radiation on the rest of the device, but that's probably manageable.
- Uranium-235: Half-life of about 700 megayears. Has a whole decay-chain with (much) shorter half-lives than itself, but you'll mainly accumulate Protactinium-231 (half-life about 32 kiloyears). Thanks to the longer half-life, it's far less active than the plutonium, so if you can handle that, you'll be fine.
- Deuterium: Stable.
- Tritium: Half-life of about 12 years, decays to helium-3 which is stable, and absorbs neutrons, hindering the reaction instead of helping it. Thoroughly gone by your time, and you can't make it. We can't use it. (on real weapons where it is used, it is kept in canisters that have to be replaced regularly)
- Lithium-deuteride: Stable. Physically that is. You do need to keep it sealed, because it won't like water or oxygen.
- Uranium-238: Half-life of about 4 gigayears. Don't worry about it.
- Polonium-210: Half-life of 210 days. We definitely can't use it.
- Beryllium: Stable
- Chemical explosives: These are one of our big issues. It's unlikely that any of our current high-explosives will remain in usable condition over 600 years.
- Electronics: Even more so. While solid-state electronics are remarkably tough, other components (such as large capacitors) are not. It might be possible to construct a "firing-system-on-a-chip", but I have my doubts that it will last 600 years.
Design
Secondary
The secondary is the easy bit. No chemical reactions are required, so it can be made chemically stable
- Lithium-deuteride fusion fuel
- Plutonium-239 'sparkplug' in the center of the fusion fuel
- Tamper encasing the fusion fuel. Usually made of Uranium-238. Can also be made from Uranium-235 for somewhat higher (and dirtier) yields, or lead, for cleaner weapons (far less fission, so less possible fallout).
- Possibly some kind of 'window' controlling the flow and timing of neutrons from the primary to the sparkplug
The secondary is compressed by ablation of the tamper. The ablation is controlled by the geometry of the primary, the secondary and the casing. A fission reaction is initiated in the sparkplug by a flood of neutrons from the primary's reaction. This fission reaction then provides the neutrons to breed tritium from the lithium and the heat required to start deuterium-tritium fusion. The fusion reaction then provides more heat and fast neutrons to fission not just the sparkplug but also the tamper.
If built with enough margin, there is no reason the secondary couldn't last 600 years and still be functional.
The casing
The purpose of the casing is to internally reflect the radiation from the primary in such a way that the secondary is efficiently compressed. Some devices for controlling the flow of neutrons from the primary to the secondary may also be present.
There is probably some kind of foam filling most of the casing to keep the primary and secondary in position. This is something that will probably need to be replaced. Metal or ceramic struts could also be used for holding things in place, and while that changes the way the radiation flows through the casing, it can probably be designed around, and will last far longer.
The primary
Here the real problems start. There are two types of fission devices: gun-type and implosion-type. The idea is that you want a sub-critical assembly to transition to super-criticality very quickly (well within the expected time for spontaneous neutron emission in your fuel. If the reaction starts too early, it may force the critical assembly apart, ending the reaction and drastically reducing the yield). The high rate of spontaneous fission (causing neutron emission) from other plutonium isotopes is why gun-type weapons exclusively use uranium.
Gun-type
The gun-type is far simpler, simply assembling two sub-critical parts at high speed using a gun. The downsides are safety (there are a lot of ways it can go off accidentally, or turn into an uncontrolled nuclear reactor), low efficiency (lots of fuel needed for relatively low yield) and a single large dimension (all US designs were over a meter long, due to the gunbarrel).
The minimum barrel length depends on the quality of your explosives and the acceptable risk of predetonation. If you're willing to accept a very long device (several meters) and a higher risk of predetonation, even black powder could work.
Implosion-type
The implosion-type requires highly coordinated detonation of specifically shaped explosive lenses. This compresses the (hollow or solid) sphere of fissile fuel to supercriticality, and greatly increases the reaction rate. Such a design can be boosted (fusion fuel injected into the core to produce more neutrons, increasing efficiency), but this is not required.
What is required is at least two (spherical types use far more, but with clever engineering, this can be reduced) very accurate detonators, carefully machined explosive lenses, and simultaneous ignition of those detonators. Replacing the lenses, detonators and electronics is probably beyond the capabilities of your cult.
Initiator
The reaction in the primary is started by an initial burst of neutrons. In early weapons, this was done by crushing a capsule of beryllium and polonium-210. Later designs used a neutron generator that fired tritium ions at a deuterium target, producing a tiny fusion reaction that generates neutrons.
We can use neither polonium nor tritium. A deuterium-deuterium reaction is feasible, though far less efficient, but whether a fusor device will survive long enough (including driving electronics) is a big question.
A gun-type weapon does not actually require an initiator though. After the parts have been assembled and have achieved supercriticality, the reaction will start, it will just be less efficient if it starts with a few spontaneous emissions, rather than a coordinated flood.
Conclusion
A black powder-driven fission device is probably feasible, if you don't plan on carrying it anywhere. It could have a breach where the Cult leader can place the charge of holy powder prior to firing.
Once you have a fission reaction of sufficient size, it could be possible to use that to drive a secondary. This would require having the barrel stick into the (very sturdy, and very well-sealed) radiation casing. There may be all sorts of reasons why this won't work, but it could be possible.
It may therefore be possible to design and build a two-stage device with a black powder-driven gun-type primary, which can be maintained and fired with very basic explosives knowledge. To my knowledge, no such device has ever even been designed though, and the only purpose I can imagine would be an apocalypse-proof operate-in-person self-destruct-your-entire-city device.
This type of device would have to be designed this way though, you can't just cobble it together from leftover parts without a very deep understanding of how everything works and the ability to calculate what would happen.
If this is indeed what you need for your story, you now get to figure out why on earth someone (or rather, some organization) designed and built a device like this.