Sie wollen also als Eingabe eine rationale Funktion, die nicht in der Standarddarstellung eingegeben werden soll (negative Exponenten) und als Ausgabe dennoch den Rechenweg einer quasi unechten Polynomdivision.
So schön es wäre, wenn polynom.sty sowas alles kann; ich würde sagen, (spätestens) hier ist der Punkt erreicht, wo man ein richtiges CAS bemüht, z.B. Sage(math) bzw. SageTeX für die Darstellung im Dokument.
Aber auch hier würde ich sagen, dass es für solche speziellen Wunschausgaben auch nichts Fertiges gibt, man stattdessen ein kleines Programm schreiben muss, was die gewünschten Zwischenschritte ausgibt.
polynom.sty ist m.E. brauchbar für nicht zu schwere Beispiele in einem Dokument, nicht aber für das wissenschaftliche Rechnen o.ä. Ich würde sogar behaupten, dass hier polynom.sty überhaupt noch etwas ausgibt (wenn auch das Richtige im Ergebnis, in der Rechnung nicht) ist nahezu ein Glückstreffer, wenn man mit derlei Eingaben weiterspielt, wird er es bald nimmer mitmachen.
Wenn man es übrigens in der normalen Art und Weise eingibt, macht er es schon:

- 5555555.png (6.88 KiB) 3454 mal betrachtet
\documentclass{article}
\usepackage{amsmath}
\usepackage{polynom}
\begin{document}
\polyset{style=C, div=:,vars=z}
Alt: \polylongdiv{1+2z^{-1}}{1+2z^{-1}+4z^{-3}}
Normal: \polylongdiv{z^3 +2 z^2}{4 + 2 z^2 + z^3}
\end{document}