I am going to answer entirely on the logic side, disregarding the connection to religious issues.
There are a wide range of logics available.
Call Classical First-Order Logic (CFOL) the logic that is usually taught in contemporary introductions to formal logic. It has several properties of relevance here. For example: from P & ~P, everything follows, P v ~P is a logical truth, and quantification (statements like 'There is an x such that Fx' and 'For all x ....) range only over objects (hence 'FO').
There are various extensions of CFOL.
Higher order logics allow one to quantify over properties of objects (Second Order Logic), or properties of properties (Third Order Logic), etc. SOL is needed to state the full generality of the principle of mathematical induction in arithmetic, to articulate a formal theory of arithmetic such that the natural numbers are (up to isomorphism) the unique model of the theory, and to state in full generality Leibniz's laws of identity. For each order above first, there are alternative semantics available which induce different rules of inference.
There are various modal logics, which add operators for notions like metaphysical possibility and necessity, temporal relations, epistemic notions, and notions of permissibility and obligatoriness. Even for metaphysical necessity (likely the best studied modal logic), there are multiple logics available, depending on the underlying view about the relationships between possibility and necessity.)
There are also many restrictions of CFOL.
Intuitionistic logic gives up on the general truth of P v ~P, doesn't in general allow you to conclude P from Q & ~Q (though ~P still follows), and treats quantification somewhat differently.
Relevant logics require more for the truth of P --> Q than the CL condition that either P is false or Q is true in order to avoid the paradoxes of material implication. (Along the way, it looses the principle of Disjunctive Argument: From P v Q and ~P, Q.)
Paraconsistent logics drop the principle that everything follows from a contradiction (in a fashion rather different than does Intuitionistic logic); it is motivated in part by the idea that there may be true contradictions.
There are multi-valued logics which assign, in their semantics, more than 2 truth-values (even for 3 values, there is more than one way to proceed) and adopt corresponding principles of proof. These are not in general classifiable as restrictions or extensions of CFOL; it depends upon the details of the particular multi-valued logic.
That is just a very quick (hand-wavy, really) survey of some of the better know alternatives to CFOL. It is, however, sufficient to establish that not only are alternative logics possible, they are actual. However, none of these (including CFOL) are universally accepted as logic; the demarcation of the bounds of what really counts as logic is one of the central problems in the philosophy of logic.