If all the believers are right and there really is a hell and the criminal is oblivious to all of it and never repents then death could be considered a penalty.
Good point ranthi,
Unbelievers should be executed because:
A) If there is a Hell they will go straight there.
B) If there isn't they forfeit the only life they'll ever have.