Wildcard Domains with GoDaddy

Go to GoDaddy's DNS Manager, the first table on top should say A(Host), click the button under that first table that says Quick Add. In the first text field, enter an asterisk (*), in the second one, the IP address to redirect to (the same one you have for the @ record on top). Click "Save Zone File" on top-right and confirm.

This creates a catch-all record to anysub.yourdomain.com.

Good luck.

I just tried it today and it seems that it's now possible to create wildcard cnames in GoDaddy.

GoDaddy > ... > DNS Manager -> Zone File Editor (Edit Zone)

Then under CNAME (Alias) panel > Quick Add

Host: *
Points to: yourapp.herokuapp.com

Or

Host: *.dev.herokuapp.com
Points to: yourapp.herokuapp.com

Then click on "Save Zone File" and wait a few minutes.

I remember getting this "Host not found 3(NXDOMAIN)" error myself not so long ago. Not anymore. Any subdomain other than those listed explicitly in either A or CNAME are redirected as expected.