Even we had deadlock proplem in one of our SQl Job. We did following. Used Begin Try End Try block & Begin catch End catch block. Use a flag in the permanent table which indicated processed or not. When trying to rerun run only those which is not processed. This way second time when you run it processes only which are not processed.

You cannot run exe which has GUI. You can run exe which is running in background process.