They are indeed brutal, but as others have mentioned, they aren't invincible. A single failed save from a S 8+ weapon will cause instant death.
However, to split hairs, it will take 7-8 powerfist attacks on average, or 5-6 S8+ shooting attacks.
Each shot has a 2/3 chance of hitting x 5/6 chance of wounding x 1/3 chance of getting by his invulnerable save, resulting in a 10/54 chance of each shot killing him. So statistically, you'll need either 5 or 6 shots to do it.
Since the Doom has WS4, close combat attacks are a little bit worse off, with a 1/2 chance of hitting instead of 2/3, resulting in a 5/36 chance of each attack killing him, which means you'll need 7-8 powerfist attacks to do it.
If you ask me, shooting is the way to go do him in. Good luck!