Is it possible via an Office 365 Nintex Workflow to create an Active Directory Account on an on-premise Domain

yes but... It would require something in you on premise that is capable of provisioning new AD user and has web service

For example you can try that solution:

1. In your on premise you have a Nintex Workflow set to have an external start.
2. In your O365 workflow you call your on premise workflow passing the require data to it.
3. The on premise workflow has an action to provision new user in AD.

BUT -  to do it that way you must have Nintex Enterprise license, because the AD actions are only available there.

Regards,

Tomasz