Node creation and reference on parent node creation

I am building a site where users would be creating nodes and subnodes. The subnodes are linked to the parent node by a node reference field on the parent node. The basic system of create subnodes, write down node ids or titles, and use the text box on the parent node too complicated for these users.

Here are my requirements:
* Workflow must be simple and streamlined. With theming, the basic node add dialog will work.
* All nodes and subnodes must be created simultaneously after clicking one submit button. This is because if a user decides to abort the addition process halfway, the site would get left with subnodes without parents.
* No javascript popups. This is such basic functionality that I do not want to depend on javascript to do it.

The parent and child nodes all have cck fields and taxonomy.

I have tried two different approaches so far. The first was to create a custom form that grabbed the node add forms and converted them into one super form. This turned out to be very difficult and very fragile, due to the complexity of the node add forms. The second approach was to embed the node add form in a node reference widget. This seems to be impossible.

Does anyone have any other ideas how I should go about this? I really want to avoid using the form api to create a custom form that has to be modified every time a field is added, removed, or changed.

Thanks!