The argument you give generalizes to show that
$$p(n) \ge (k+1)^{ \lfloor \sqrt{ n/k } \rfloor }$$
for any positive integer $k$. We repeat the same argument, but instead of subsets of $\{ 1, 2, ... \lfloor \sqrt{n} \rfloor \}$ we allow multisubsets of $\{ 1, 2, ... \lfloor \sqrt{n/k} \rfloor \}$, where each element occurs with multiplicity $0$ through $k$.
So how much better is this? The actual asymptotic value of $\log p(n)$ is known to be $\pi \sqrt{ 2n/3 }$, so $C \sqrt{n}$ where $C \approx 2.565...$. The argument you give shows that $C \ge \log 2 \approx 0.693...$. The generalization above shows that $C \ge \frac{\log (k+1)}{\sqrt{k}}$. Some numerical experimentation shows that this attains a maximum at $k = 4$, giving $C \ge \frac{\log 5}{2} \approx 0.805...$. So this is a little better, but still a long way to go.
Edit #2: Here is an argument along the above lines which gives $C \ge \sqrt{2} \approx 1.414...$. We will now allow the positive integer $k$ to occur with a multiplicity from $0$ to $m_k - 1$ for some $m_k \ge 1$. This produces a partition in the same way as above provided that the sum constraint $\sum k (m_k - 1) \le n$ is satisfied, and we get $\prod m_k$ partitions this way. A heuristic calculation using Lagrange multipliers suggests that we want $m_k$ to be proportional to $\frac{1}{k}$; we will in fact take
$$m_k = \left\lfloor \frac{m}{k} \right\rfloor$$
if $k \le t$ (and $m_k = 1$ otherwise) for some $m, t$ satisfying certain constraints. First, since we must have $m_k \ge 1$, we need $m \ge t$. Second, the sum constraint $\sum k (m_k - 1) \le n$ gives
$$mt - \frac{t(t+1)}{2} \le n.$$
We will choose $m, t$ later. First, taking the logarithm of the number of partitions gives
$$\sum_{k=1}^t \log \left\lfloor \frac{m}{k} \right\rfloor.$$
We can write this as approximately (ignoring floors now)
$$\sum_{k=1}^t (\log m - \log k) = t \log m - \sum_{k=1}^t \log k.$$
(This is an overestimate but I believe it does not affect the asymptotic.) The estimate $\log n! \approx n \log n - n + O(\log n)$ gives that this is asymptotically
$$t \left( \log \frac{m}{t} + 1 \right) + O(\log t).$$
Now to optimize $m, t$. First, we can replace the sum constraint with a constraint
$$mt - \frac{t^2}{2} \le n$$
which is easier to deal with. Taking $t = a \sqrt{n}$ gives
$$m \le \left( \frac{1}{a} + \frac{a}{2} \right) \sqrt{n}$$
so we can just take $m$ to be this value (ignoring floors again); the constraint $m \ge t$ is now equivalent to the constraint $a \le \sqrt{2}$. The logarithm of the number of partitions we get now takes the form
$$a \sqrt{n} \left( \log \left( \frac{1}{2} + \frac{1}{a^2} \right) + 1 \right) + O(\log n)$$
which gives
$$C \ge a \left( \log \left( \frac{1}{2} + \frac{1}{a^2} \right) + 1 \right).$$
Some numerical experiments suggest that the RHS is increasing for $a \le \sqrt{2}$, and taking $a = \sqrt{2}$ gives $C \ge \sqrt{2}$ as desired.
I do not think this type of argument can be pushed substantially further without some new idea.
The proof of the asymptotic formula for the partition function given by Hardy and Ramanujan was "the birth of the circle method", and used properties of modular forms. Erdös was trying to give a proof with elementary methods (he also gave a so-called elementary proof of the PNT with Selberg). He succeeded in 1942 to give such a proof, but only with "unknown" constant $a$, see here. Afterwards Newman gave a "simplified proof", and obtained also that $a=\frac{1}{4n\sqrt{3}}$, see here.
There are several "modern" references now, which give an elementary proof of the asymptotic formula for $p(n)$. Here are two references:
M. B. Nathanson: On Erdös's elementary method in the asymptotic theory of partitions.
Daniel M. Kane (was misspelled as "Cane"): An elementary derivation of the asymptotic of the partition function.
Instead of using modular forms etc. the elementary method of Erdös only uses elementary estimates of exponential sums and an induction from the identity
$$
np(n)=\sum_{ka\le n}ap(n-ka).
$$
Best Answer
A polynomial of degree $a$ is $O(n^a)$. If $p(n)$ is eventually greater than $n^{a+1}$, then $p(n)$ is not $O(n^a)$ and therefore is not bounded by any polynomial of degree $a$. Since this holds for all $a$, $p(n)$ is not bounded by any polynomial.
Let $\langle i_1,\ldots,i_{a+1}\rangle$ be any non-increasing sequence of positive integers such that $i_1\le\left\lfloor\frac{n}{a+1}\right\rfloor$. Since $i_k\le i_1\le\left\lfloor\frac{n}{a+1}\right\rfloor\le\frac{n}{a+1}$ for $k=1,\ldots,a+1$, $$\sum_{k=1}^{a+1}i_k\le(a+1)\cdot\frac{n}{a+1}=n\;.$$ Let $s=\sum_{k=1}^{a+1}i_k$; then $n-s\ge 0$. If $s=0$, then $\langle i_1,\ldots,i_{a+1}\rangle$ is a partition of $n$ into $a+1$ parts. If $s>0$, we’ll fill that out with $n-s$ parts of size $1$ to make the partition $$\langle i_1,\ldots,i_{a+1},\underbrace{1,\ldots,1}_{n-s}\rangle\;,$$ abbreviated in your proof as $\langle i_1,\ldots,i_{a+1},1^{n-s}\rangle$. We’re going to count the partitions of $n$ that have this form for some such sequence $\langle i_1,\ldots,i_{a+1}\rangle$. We know that $s\le\left\lfloor\frac{n}{a+1}\right\rfloor$ because we only consider sequences $\langle i_1,\ldots,i_{a+1}\rangle$ for which that’s the case.
Think of the sequence $\langle i_1,\ldots,i_{a+1}\rangle$ as a multiset of $a+1$ elements $i_1,\ldots,i_{a+1}$, each of which is a positive integer no larger than $\left\lfloor\frac{n}{a+1}\right\rfloor$. The set of all such sequences can in this way be identified with the set of all multisets of cardinality $a+1$ chosen from the set $\left\{1,\ldots,\left\lfloor\frac{n}{a+1}\right\rfloor\right\}$, and there are $$\left(\!\!\binom{\left\lfloor\frac{n}{a+1}\right\rfloor}{a+1}\!\!\right)=\frac{\left\lfloor\frac{n}{a+1}\right\rfloor^{\overline{a+1}}}{(a+1)!}=\binom{\left\lfloor\frac{n}{a+1}\right\rfloor+a}{a+1}\tag{1}$$ of those. (There’s an error in your proof at this point: that ugly numerator should have $a+1$ factors, not $a$, so the last one should be $\left\lfloor\frac{n}{a+1}\right\rfloor+a$.)
Parts (2) and (3) showed how to construct $\left(\!\!\binom{\left\lfloor\frac{n}{a+1}\right\rfloor}{a+1}\!\!\right)$ partitions of $n$, so $$p(n)\ge\left(\!\!\binom{\left\lfloor\frac{n}{a+1}\right\rfloor}{a+1}\!\!\right)\;.$$ To justify the strict inequality in your proof, we may simply note that we counted only partitions with at least $a+1$ parts.
Each factor in the numerator of $(1)$ is at least $\left\lfloor\frac{n}{a+1}\right\rfloor$, so $$p(n)>\frac1{(a+1)!}\left(\left\lfloor\frac{n}{a+1}\right\rfloor\right)^{a+1}\ge\frac1{(a+1)!}\left(\frac{n}{a+1}-1\right)^{a+1}\tag{2}\;.$$ The righthand side of $(2)$ is a polynomial in $n$ of degree $a+1$, so it’s $\Theta(n^{a+1})$, i.e., grows with order $a+1$.