You would first need to have WordPress multisite enabled: http://codex.wordpress.org/Create_A_Network
Then you could use something like ProSites (totally optional, you can allow them to create sites without this, this just lets you setup a Pay to Blog system) and Affiliate to allow your members to create their site.
We even have a great Template Plugin. http://premium.wpmudev.org/project/new-blog-template/
This: Members can not create new subdomains
Would be tricky, unless you wanted to manually create the site yourself, then you'd need to build a contact/request form instead.
As far as being behind a paywall, that's a little inaccurate. We do have a membership requirement, but that is only for ongoing support and upgrades. What you pay for is the team behind the plugins. You can cancel membership at any time and use the plugins as long as you would like on as many sites as you wish.
The only two exceptions to the rule are the two plugins that require a live API to host, and those are our whitelabel videos and antisplog.
Lemme know if you have any more questions!