Update. I've improved the argument to use only the consistency of $T$. (2/7/12): I corrected some over-statements previously made about Robinson's Q.
I claim that for every statement $\varphi$, there is a variant way
to express it, $\psi$, which is equivalent to the original
statement $\varphi$, but which is formally independent of any
particular desired consistent theory $T$.
In particular, if $\varphi$ is your favorite natural open question,
whose truth value is unknown, then there is an equivalent
formulation of that question which exhibits formal independence in
the way you had requested. In this sense, every open question is
equivalent to an assertion with the property you have requested. I
take this to reveal certain difficult subtleties with your project.
Theorem. Suppose that $\varphi$ is any sentence and $T$ is any consistent theory containing weak arithmetic. Then there is another sentence $\psi$ such that
- $\text{PA}+\text{Con}(T)$ proves that $\varphi$ and $\psi$ are equivalent.
- $T$ does not prove $\psi$.
- $T$ does not prove $\neg\psi$.
Proof. Let $R$ be the Rosser sentence for $T$, the self-referential assertion that for any proof of $R$ in $T$, there is a smaller proof of $\neg R$. The Gödel-Rosser theorem establishes that if $T$ is consistent, then $T$ proves neither $R$ nor $\neg R$. Formalizing the first part of this argument shows that $\text{PA}+\text{Con}(T)$ proves that $R$ is not provable in $T$ and hence that $R$ is vacuously true. Formalizing the second part of this argument shows that $\text{Con}(T)$ implies $\text{Con}(T+R)$, and hence by the incompleteness theorem applied to $T+R$, we deduce that $T+R$ does not prove $\text{Con}(T)$. Thus, $T+R$ is a strictly intermediate theory between $T$ and $T+\text{Con}(T)$.
Now, let $\psi$ be the assertion $R\to (\text{Con}(T)\wedge \varphi)$. Since $\text{PA}+\text{Con}(T)$ proves $R$, it is easy to see by elementary logic that $\text{PA}+\text{Con}(T)$ proves that $\varphi$ and $\psi$ are equivalent.
The statement $\psi$, however, is not provable in $T$, since if it were, then $T+R$ would prove $\text{Con}(T)$, which it does not by our observations above.
Conversely, $\psi$ is not refutable in $T$, since
any such refutation would mean that $T$ proves that the hypothesis
of $\psi$ is true and the conclusion false; in particular, it
would require $T$ to prove the Rosser sentence $R$, which it does not by the Gödel-Rosser theorem. QED
Note that any instance of non-provability from $T$ will require the consistency of $T$, and so one cannot provide a solution to the problem without assuming the theory is consistent.
The observation of the theorem has arisen in some of the philosophical literature you may
have in mind, based on what you said in the question. For example, the claim of the theorem is mentioned in Haim Gaifman's new
paper "On ontology and realism in mathematics," which we read in my course last semester
on the philosophy of set theory; see the discussion on page 24 of Gaifman's paper and specifically footnote 35, where he credits a fixed-point argument to Torkel Franzen, and an independent construction to Harvey Friedman.
My original argument (see edit history) used the sentence $\text{Con}(T)\to(\text{Con}^2(T)\wedge\varphi)$, where $\text{Con}^2(T)$ is the assertion $\text{Con}(T+\text{Con}(T))$, and worked under the assumption that $\text{Con}^2(T)$ is true, relying on the fact that $T+\text{Con}(T)$ is strictly between $T$ and this stronger theory. The current argument uses the essentially similarly idea that $T+R$ is strictly between $T$ and $T+\text{Con}(T)$, thereby reducing the consistency assumption.
In fact all true arithmetical sentences have weak classical realizers. Namely, a true arithmetical sentence $\psi$ $$\forall x_1\exists y_1 \ldots \forall x_n\exists y_n \theta(x_1,\ldots,x_n,y_1,\ldots,y_n)$$
is weakly realized by $(e_1,\ldots,e_n)$, where $\Phi_{e_i}^{\vec{g}}(y_1,\ldots,y_{i-1})$ performs an unbounded search for a tuple $(y_i,\ldots,y_n)$ such that $\theta(g_0(),\ldots,g_n(y_1,\ldots,y_n),y_1,\ldots,y_n)$ is true and then outputs $y_i$ from the first found tuple. This works since for any $g_1\colon\mathbb{N}^0\to\mathbb{N},\ldots,g_n\colon \mathbb{N}^{n-1}\to\mathbb{N}$ the sentence $\exists y_1,\ldots, y_n \theta(g_0(),\ldots,g_n(y_1,\ldots,y_n),y_1,\ldots,y_n)$ is true.
Best Answer
Per the comments, we're looking at deduction in some system based on the $\omega$-rule as opposed to standard first-order deduction (or Henkin semantics or etc.). There's a technical issue here - in my experiene the $\omega$-rule is usually formulated for first-order arithmetic sentences, so I'm not sure what it means to deduce a $\Pi^m_n$ or $\Sigma^m_n$ sentence using the $\omega$-rule for $m>0$ (this may be in the linked paper I don't have access to) - but in fact there's a coarse calculation which will apply to any reasonable interpretation I can think of:
Every version of the $\omega$-rule I can think of is $\Pi^1_1$ - roughly, "the $\omega$-consequences of $T$" will always be $\Pi^1_1$ relative to $T$. If (for example) we start with the true $\Pi^1_1$ theory of arithmetic, we won't even get all the true $\Sigma^1_1$ sentences since the true $\Sigma^1_1$ theory of arithmetic isn't itself $\Pi^1_1$ (more broadly, the projective hierarchy doesn't collapse).
Now your notion of specialness gives us only two tools for "climbing up" the syntactic hierarchy: deduction and complementation. In terms of Turing degree this means that we're not going to escape the $\omega$th hyperjump of $\emptyset$, which is a tiny subclass of $\Delta^1_2$.
(This is contra a silly claim I made originally - the point is that "$\Pi^1_1$ in $\Sigma^1_1$" is much weaker than "$\Pi^1_2$," or more concretely that $\mathcal{O}^\mathcal{O}$ is not $\Pi^1_2$ complete. The sense in which applying the $\omega$-rule "adds a $\Pi^1_1$" seems to follow the former pattern if set up in a natural way. That said, I see no sense at all in which we can get outside the analytical hierarchy.)