In my personal opinion, you need to switch hosting providers. If I understood you correctly, they are charging for subdomains which are otherwise completely free to create and use.
Anyway, no, there should be no additional cost for inserting this entry (other than the one they appear to charge). They only reason they wouldn't do this is so they can profit from the fact you cannot be bothered to get a better deal elsewhere. I do not know of a server setup that wouldn't support this very simple feature (that is, Apache and Bind support it out of the box).
How to do it:
*.example.com record need not be a DNAME record specifically. What you essentially want is just a normal A record that points
126.96.36.199 (where the IP represents the shared IP the website is hosted on. If you're not sure what it is, just look at your
example.com IN A record - it has to resolve to it):
*.example.com IN A 188.8.131.52
and then Apache will take it from there, just setup the
VirtualHost to have the correct entry (I think it's
ServerName) to be
*.example.com and everything will match correctly (i.e. it'll load the correct
Just so you know: you cannot circumvent the fact that Apache will need to be (manually) configured. Some hosting providers may not do this, and if they don't, leave!