Если у вас и регистратор и хостер — одна и та же компания (к примеру как тот же GoDaddy), но при этом они позволяют только менять NS сервера, но не дают возможности менять на своих NS серверах ничего, то тут и вправду компания не сильно качественная (ну правда, я с таким не встречался). И я бы рекомендовал сменить хостинг как минимум, а как максимум — еще и сделать трансфер домена к другому регистратору. Это был бы для меня правильный план. Действенный план на сейчас — это использовать бесплатные NS сервера, как к примеру предоставляет EveryDNS. Но есть одно но. Ведь вам нужно у них потом будет и A запись сделать, сославшись на какой-то айпи. А судя по тому что вам не позволяет ваш хостер, это какой-то shared хостинг без какого либо намека на неизменность айпи. Потому если вашего хостера что-то укусит или они что-то изменят — сайт компании перестанет быть доступным пока вы все руками на EveryDNS не измените вновь. Решайте.