Categories on a Front-end form
This isn't possible with the build in FEEF functionality.

You can however achieve this via a Plugin. What you need to do is to listen to the onBeforeSave event and make an if-statement to check if the entry is being added to your section. Then you can run a loop that checks all the submitted categories against your database and adds new entries for the categories that doesn't exist and re-populates your EntryModel with the new category ID's before insertion.