I have domain in one company, with an specific NS entries, but I don't want changes the NS entries.
The server is in another company with public IP.
If I want to point from my domain to the server, is enough with adding an A record into the domain company, that A entry would point to my public IP.
Is that OK?
How long it takes the changes?
How can I trace the A record propagation?
Use your domain companies tools to create an A record that points to the public IP address of your server. The changes can take quite some time perhaps up to 72 hours for global coverage but would generally be less. You can try tools like this to see how your A record is propagating.
Adding a new A record for a new domain (host) should propagate quite quickly. Initial queries will go to your nameserver rather than caches. Changes to that domain will depend on the TTL for the domain.
There may be some delay with synchronizing the nameservers, but many setups use notify. This will speed things up.
The main problem will be possible negative caching. This should not be much of a problem, as noone should have been looking for the domain.