Prove that a counterexample exists without knowing one
Statement: "There are no primes greater than $2^{60,000,000}$". No known counter-example. Counter example must exist since the set of primes is infinite (Euclid).
According the Wikipedia article on Skewes' number, there is no explicit value $x$ known (yet) for which $\pi(x)\gt\text{li}(x)$. (There are, however, candidate values, and there are ranges within which counterexamples are known to lie, so this may not be what the OP is after.)
Another example along the same lines is the Mertens conjecture.
A somewhat silly example would be the statement "$(100!)!+n+2$ is composite." It's clear that $S(n)$ is true for all "small" values of $n\in\mathbb{N}$, and it's clear that it's false in general, but I'd be willing to bet a small sum of money that no counterexample will be found in the next $100!$ years....
(Note: I edited in a "$+2$" to make sure that my silly $S(n)$ is clearly true for $n=0$ and $1$ as well as other "small" values of $n$.)
Assume some enumeration of all formulas in first-order peano arithmetic, and let $S(n)$ be the statement
The $n$-th formula is not provable in, but consistent with, first-order peano arithmetic, and isn't any of the known such formulas $\mathcal{F}$."
Assuming that the set of known such formulas $\mathcal{F}$ is recursive (meaning that for any given formula, one can decide whether it is in $\mathcal{F}$ or not), there is always such a formula. Otherwise, there would be a recursive and complete extension of PA, which contradicts the incompleteness theorem.
Update: According to this, recursive can be relaxed to recursively enumerable in the above. Thus, "knowing" a counter-example doesn't need to imply that, given a formula, we can decide whether it is a known counter-example. Instead, it's sufficient that there be an algorithm which produces these counter-examples one by one, which seems like a very natural definition for "knowing a counter-example". We then know that there must always be counter-examples that the algorithm does not generate.