How to use a custom nameserver for my domain (like ns1.mydomain.com, ns2.mydomain) instead of ns1.hostingcompany.com, ns2.hostingcompany.com? Will a CNAME help?
Yes, you do this by setting up a CNAME as long as you can maintain the DNS entries for the domain.
Setup varies depending on your DNS servers.
ns1 CNAME points to IP or servername.mydomain.com in the setup
You need go for VPS or higher plan. If you go for fully managed VPS this nameserver will be done freely by your hosting provider.
A fully managed vps can start from $10-$50.