Lets explain a few things first:
Nameserver records are typically maintained by the domain registrar. (i.e. who the domain-name was purchased from.) If you don't own the domain-name directly... you might have a battle on your hands to get ownership back. It is not unheard of for shady companies to hold your domain-name hostage.
Most registrars will typically allow you to do one of two options:
- Point the SoA or NS records to another dns hosting company (or your own private DNS servers)...
- Offer/include their own DNS hosting services for your domain. It might be a simple process to talk to them and point it back to their own DNS servers.
You can typically look at your DNS records to figure out who the registrar is with online tools like nwtools.com. But if you don't actually own the domain... you might need to fight in court or pay them off, or even just abandon hope and buy a new domain.
Websites need more than nameservers to work. You'll also need "A" records to point to the IP of your webservers. An "A" record is simply a record that takes the hostname and translates that to an IP. If this company you are leaving is also the webhost... you'll need to add your own A records that point to your new hosting company's webservers. (most webhosting companies will work with you on getting the right records pointed to the right IPs)
And of course... if you don't have a webserver, (or the content from your old webhosting company) you'll need to rebuild your website.
