It means _without_, it is formed by the [NegativeForm] + zu" and means "without doing".
"~zu ni" is the same as "~nai de".
although i'm not sure of the actual probability of native speakers using such a phrasing, strictly grammatically speaking, 信じられざる話 would be the correct form. in traditional japanese grammar, ず is called 終止形 (collective term for verbs and adjectives at the end of sentences). the 連体形 (modifying nouns (体言)) of ず is ざる. in modern japanese, the 終止形 (ない） and the 連体形 (ない) are the same, so one doesn't think in those terms most of the time, but when using lingering elements from classical japanese, they are important. however, ざる-ending expressions, though not restricted to written japanese, have a rather formal sound to them.
Can you make this a adjective? Like, let's say: Shinjirarenai hanashi (The story that is not believed) Could you say: Shinjirarezu hanashi
信じられず comes up in google with quite a few hits, but this is a verb. "without believing". I think your example might be an adverb - as you are using it to modify another verb? eg: 幼い頃に母に捨てられ、愛を信じられずに育ったカン・ジェホは、働きながら大学に通う苦学生。