How Long Will A DNS Change Take
Solution 1:
Theoretically everyone should see the updated A record somewhere between instantly and the relevant TTL value. Most registrars set the TTL to 24 hours IIRC, so for 24 hours some people will see the old address and some will see the new one and by 24 hours after the change everyone should have the new address, with some instead using a lower value like 4 hours.
If you have access to change the TTL values (i.e. you run you own DNS servers) then you can reduce the TTLs down to something small a day or so before you make your change so the propogation period is much lower.
I say "theoretically" above as there will always be some bugs, glitches, and badly configured caches out there that will mean some users will not see the change for longer. This is especially true if you use very small TTLs as there are still some ISPs out there with DNS caches that ignore TTLs below a given value.
Another thing to look out for is delays between your registrar's DNS control panel and their DNS servers. For instance I noticed that changes made to domains managed by 123-reg.co.uk can take up to an hour to appear on their DNS servers, which is an extra hour on top of the TTL value that you'll have to account for.
Solution 2:
It depends on how long the clients are caching the DNS information which should be according to the TTL value. However, since the client determines how long to cache the information, you can't really be sure (after all clients can do manual resolution and thus ignore TTL completely).
Solution 3:
When I know I'm coming up on an IP address change, several days ahead of time, I typically lower my TTL value to something less than I would normally use. That way, the change propagates faster when I do make it. Then, I kick the TTL back up again.
Solution 4:
It's generally <= the TTL, but some clients and DNS proxies cache the old setting longer than the TTL.