В подавляющем большинстве случаев хостер VPS предоставляет и бесплатную услугу dns-хостинга.
Но я бы не рекомендовал их использовать (за исключением случая очень низкого бюджета) ибо по разным причинам (от удобства и надёжности до безопасности) лучше использовать нормальные платные, специализированые dns-хостинги. Раз Вы пишете "не Россия" то могу посоветовать cloudns и dnsmadeeasy.