Buahaha. So I used 4zb4's mustard gas trick with a twist. I was going to use the puppy but he died early on, so I just bought the slave from the shop.
Then I got him to stand right in front of Petrus and threw the mustard gas at him. The gas exploded, landing on Petrus's square as well. Apparently I was wrong earlier when I thought the gas doesn't affect Petrus. I just had to sit and wait for a while for him to die. Surprisingly, picking up his nut didn't constitute stealing, so nobody came after me (I didn't want to risk taking his other stuff). Also, throwing the grenade at the slave didn't make him angry, he was still loyal.
Anyways, I present to you a 1,652 turn, 1,476 point victory. It would even be possible to beat it more quickly, since I actually explored UT 1 and 2 (looking for mustard gas grenade), though I did just teleport Jenny out of the way in UT3.