I have no idea what Sobolev's proof using polynomials is, but I can suggest the following two proofs:
a) If all you want are the embedding theorms of a Sobolev space into an $L^p$ or $L^\infty$ space and do not need the sharp constant, then by far the easiest proof is using the original Gagliardo-Nirenberg inequality
$$
\|f(x)\| _ \infty \le c\left(\Pi_{i=1}^n \|\partial_if\|_1\right)^{1/n} \le c\|\partial f\|_n
$$
which can be proved using the fundamental theorem of calculus and the Fubini theorem.
Any other Sobolev inequality can be derived from this using the power rule for differentiation and the H\"older inequality.
This proof does use the simplest and original case of the Gagliardo-Nirenberg inequality, but the isoperimetric inequality plays no role at all.
b) A beautiful proof of the sharp first order Sobolev inequality using the Brenier map from mass transportation was given by Cordero-Erausquin, Nazaret, and Villani. The isoperimetric inequality is never used explicitly, but mass transportation is in a more general and powerful tool, one that implies the isoperimetric inequality.