How about the theorem "There exists at least one prime number?" There are infinitely many distinct proofs of this result, none of which includes another as a subproof. Certainly this example is trivial in some sense, but I think it is not obvious how to pin down why this shouldn't be counted.

Perhaps a better example is "There is at least one Turing machine which halts." Now - in a precise sense - any possible logical deduction is paralleled by a proof that some specific machine halts, so if there are infinitely many "distinct" deductions at all, then there are infinitely many "distinct" proofs of this proposition.

EDIT: This is entirely tangential, but I think you may find it interesting. There is a strong and fruitful tradition in mathematical logic - especially on the constructive side - of drawing analogies between (or equating) proofs and algorithms; so an at-least-vaguely related question is, "How do we tell if two algorithms are the same?" This paper (http://research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf) by Andreas Blass, Nachum Dershowitz, and Yuri Gurevich argues that there is no entirely satisfactory answer to this question. I think at least one thing to take away from this is that one should not be cavalier about the notion of "distinct proof": finding a satisfactory such notion would be a huge advancement in logic!