OK, if you are a reseller and using WHM/CPanel you can create a FULLY functional sub-domain account in the WHM which gives the 'sub-domain' all the same features as a normal domain. This includes all of the included scripts, email etc that come with the 'normal' account.
The only issue here is that you would have to create this. For a customer to create his own, as you requested, some sort of interactive script would be required.
You should be able to set-up a mysql database of taken subdomain names, and get your users to search it, if there is no results then its free, then you just update the db with names that are taken. You could even set up a whois type this make it look like a real domain.
I was thinking of doing that with a .biz domain but your not allowed to reseller it or something.