You can use the Relation Dialog module to create new entities on top of the current form when adding/editing relations. It currently integrates with the relation_add module and mimics the "Reference Dialog" behavior for relations.
After installation a new link "Add [Entity-Type]" will appear next to each autocomplete field, allowing you to create a new entity of the linkable type that will be inserted once you hit "Save". You can also add views of a special "Relation Search" type that will add more buttons to search for linkable entities right next to your autocomplete fields.