Gaza was certainly part of Judea which was unified under the common, Monotheistic Jewish belief system at the time of both the new testament stories and the Flavian conquest. This is the time-frame I'm referring to. Hope that clears up any confusion.
i can assure you they were all independent city states
gaza may well have fallen into a roman region named territory for census, it was conquered by king david and perhaps under solomon controlled by the king of all isreal but the whole region splintered into factions
israel was 12 tribes
judah was 1 then 2 when it joiined with benjamin
israel was 10 then 9 states north of judah
ahab was famous king of israel with wife jezebel and they were polytheistic
most of kings of judah were polytheistic
israel was at war with judah from end of solomon reign to exile 1
the worship of dagon was promenint in gaza
baal and ashterorth in the phoenician city states
and most of the arabs worshipedd their own different deities
it was mostly monotheistic untill the kings appeared
the judges prior to kings who were both judges and prophets unified the isreal better than kings ever did
but the temple only appeared during solomon reign
and after solomon it splintered into kin v kin tribe v tribe
solomon gave king hiram of tyre Phoenician lots of land in upper regions of his kingdo iin exchange for building his temple and it created civil war with jeroboam going up againgst solomons son reheboam
to create two opposing camps
israel and judah
most kings of israel after solomon were polytheistic?
huge portion of kings of judah were polytheistic and asherah pole worshippers
the prophets and small bands remained monotheistic but majority of region were polytheistic especially the aristocracy