Capital punishment was only for serious sins: blasphemy, adultery, etc.. From what I can see in the Bible, saying you had a preexistence isn't blasphemy. However, claiming to be one with God is quite different. In John 10:30-33 Jesus said, "I and the Father are one. The Jews took up stones again to stone him. 32Jesus answered them, "I showed you many good works from the Father; for which of them are you stoning me?" 33"The Jews answered Him, 'For a good work we do not stone You, but for blasphemy; and because You, being a man, make Yourself out to be God" (NASB).
Between John 8:59 where the Jews picked up stones to kill Jesus and John 10:30-33 where they again picked up stones to kill him, there is no mention of stoning whatsoever. John 10:31 is referencing back to John 8:59 when it says "The Jews took up stones again to stone Him." Note that they again wanted to kill Him and this time they give the reason why. They said that Jesus was claiming to be God. Now, where would they get that idea? Could it have been where he said, "Before Abraham was, I am"? Could it be from where Jesus said, "I and the Father are one" (10:30). Since they wanted to kill Him both times, it would seem that Jesus had been making some very serious claims. Or was it simply that the Pharisees misunderstood Jesus and that Jesus never did claim to be God?
But, if Jesus was not claiming to be God in John 8:58 and 10:30, then what was it that He said that warranted such a violent response from the Jews in both cases? What phrase from Jesus did the Jews react to and what 'misunderstanding' did they have about what it was Jesus said that led them to claim that he was making Himself out to be God?
The best explanation for the Jews wanting to kill Jesus is because Jesus was claiming equality with God. They considered this blasphemy.