The logic should be fully in hardware and no uC can be used. Any ideas on how to achieve that?

It seems to me that you can draw-on the standard latching on/off control circuit used to power AC motors. They use a push-button to activate the motor via a relay and, a spare contact on the relay provides the latching function that your SBC (whatever that is). The stop button interrupts the latching contact and the motor turns off: -

Image from here.

So, if your two microcontrollers could activate another relay that replaced the stop contact, I think you'd be good to go. You could probably use an opto-device that replaced the stop switch also (saving cost and space).

The logic should be fully in hardware and no uC can be used. Any ideas on how to achieve that?

It seems to me that you can draw-on the standard latching on/off control circuit used to power AC motors. They use a push-button to activate the motor via a relay and, a spare contact on the relay provides the latching function that your SBC (whatever that is) requires. The stop button interrupts the latching contact and the motor turns off: -

Image from here.

So, if your two microcontrollers could activate another relay that replaced the stop contact, I think you'd be good to go. You could probably use an opto-device that replaced the stop switch also (saving cost and space).