Being Jewish is more to do with ethnicity than religion per se , it is interesting to note that although Jesus was born in a Jewish household ,he never claimed or asserted that his religion was Judaism in the entire gospel in spite of the fact that he observed the Torah commandments. The early disciples and subsequent followers of Jesus knew this hence they never used the equivalent terms like "Yahoodi" (Aramaic), "Judaism" etc to refer to themselves.
A similar question was asked on Christianity.SE, here is a brief excerpt of the relevant portion of the answer:
19 Therefore Jesus answered and was saying to them, “Truly, truly, I
say to you, the Son can do nothing of Himself, unless it is something
He sees the Father doing; for whatever [a]the Father does, these
things the Son also does in like manner.
Jesus's religion was therefore not one of the established theologies
of the time, but rather a lifestyle of submitting to the will of the
Father. Jesus had such a close and intimate relationship with the
Father that Jesus understood the character of the Father well enough
that He could operate as the Father would do in the same situations.
Hence Jesus did not belong to any named religion of his time which he was very explicit as above but he did obey the commands of God by submitting his will to God. Thus the earlier "Christianity" itself never viewed him as a Jew by religion. Regarding the NT statement about his claim to be the "King of Jews", then he himself never claimed to be "King of Jews" as he himself never made this assertion ,but rather the Jews around him made such an allegation against him:
New International Version (©2011) "Are you the king of the Jews?"
asked Pilate. "You have said so," Jesus replied.( Mark 15:2 )
Moreover Jewish leaders prefer the designation "King of Israel", as in Matthew 27:42, Mark 15:32.
Hence Jesus never accepted this allegation of he being "King of Jews" this is the reason why the governor Pilate found no fault with Jesus as Jesus did not acknowledge that he was the "King of Jews":
Pilate washes his hands with water in front of the crowd, saying, "I
am innocent of this man's blood; you will see."
(Gospel of Matthew)