The Jewish Authorities certainly had the right to execute, by various means required under the Law. Blasphemy was punished by stoning according to Lev. 24:13-16, when in the case of a son of an Israelite woman who blasphemed, those who heard it were required to take him outside the camp and stone him. Jesus Himself did not dispute this: in the incident of the woman caught in the act of adultery, He tells the scribes and Pharisees,"he who is without (this) sin among you, let him first cast a stone at her."(John 8:3) In Matt. 23:2, He says,"the scribes and Pharisees sit in the chair of Moses, all therefore they bid you observe, that observe and do." Since Pilate's response was,"take Him and judge Him according to your Law", the Law prescribed death by stoning for blasphemy; Pilate hadn't voiced any objections for the other stonings or attempts at stoning, therefore, there was no reason to do so now. So the response of the chief priests and scribes should be interpreted,"It is not lawful to put any man to death 'in this manner-crucifixtion'.
The key to understanding the question is John 18:32,"That the saying of Jesus might be fulfilled, which He spoke, signifying what death He should die." This is because of what He said in John 12:32,"And I, if I be lifted up from the earth, will draw all men unto Me." Verse 33 says,"This He said, signifying what death He should die." We see throughout the Old Testament the Jesus's death described, Ps. 22:16,"For dogs have compassed me: the assembly of the wicked of have inclosed me: they pierced my hands and my feet." Isa. 53:5,"He was wounded for our transgressions, he was bruised for our iniquities: the chastisement of our peace was upon him; and with his stripes we are healed." In Zech. 12:10,"I will pour out upon the house of David, and upon the inhab itants of Jerusalem, the spirit of grace and of supplications: and they shall look upon Me whom they have pierced, and they shall mourn for him, as one mourneth for his only son, and shall be in bitterness for him, as one is in bitterness for his firstborn."
The cross was a Roman invention; one that exacted the maximum amount of pain, without killing or making the person unconcious. This punishment was reserved for those who were insurrectionists, like Barabbas, or those that the Romans wished to make an example of. The means of death was usually asphyxiation, as one's lungs would fill up with fluid that one could not aspirate, since that meant pushing up on the nails that held one's feet. To break the legs(of the 2 other thieves) hastened their death. With Jesus's death John witnessed a miracle: Jesus giving His spirit up to the Father, after He had spoken the last 7 sayings. When the soldier pierced Jesus's side, He saw that the blood and water had already separated-indicating that this man "had laid down his life, and had taken it up again." In John 10:18 He said,"No man taketh it from Me, but I lay it down of Myself. I have the power to lay it down, and I have the power to take it again. This commandment have I received of My Father."
So, why the cross? Because of our betrayal through Adam in the Garden of Eden, choosing 'Satan's Tree rather than the Tree of Life-Christ Himself, God through His mercy offered men a sacrifice, His Son who was 'that' Tree. Satan, in his derision and mockery made it look like something to distain, ridicule, think to oneself, 'I want no part of that...' Yet, for us who believe it is the "power of God."(1 Cor. 1:18) The other reason is "we have all sinned and gone astray."(Isa. 53:6) All of mankind, Jew and Gentile-all of Adam's seed had 'missed the mark'. Rembrandt so accurately depicts this when paints the artist holding the body of Christ taken down from the cross. Mel Gibson portrayed it when it was his hand holding Jesus's arm when the soldier drove the nails into His hand, in The Passion of the Christ. For those who embrace the cross, "despise it's shame"(Heb. 12:2), see the Tree of Life once again, bidding them to come to His feast.
For an implement of torture one would want to avoid, it has been seen the world over. Even in Atheistic Communist China, crosses are made to sell to the masses around the world. Universally it is accepted as the sign of Christ, a church would be 'naked' without one. We can clearly see the truth,"If I be lifted up from the earth, will draw all men to Me."