There're also apps like Internet Booster promising to "clear DNS cache" (amongst other things). I didn't try it out myself, and furthermore there seems no way to do only that (just one "optimize" button which "applies improvements"); also its effects might differ between devices (says the app's description) -- but it might be better than a reboot. Btw: while not mentioning root as requirement, it might still be needed.
There are several "similar apps" listed on Google Play -- but be aware that most of them include Airpush ads and/or want excessive permissions, which is why I didn't name them here.
Another possible solution (not tested by myself) I found at MadPC, seemingly quoting user8522's answer before stating:
The last option but most intensive on the user themselves unless they want to just wait the update out: Have your users go into settings -> applications -> Network Location -> Clear data
Another short howto mentions a different easy way to flush DNS (again, I didn't test this myself): Simply switch to airplane mode (oops, no network?) and back (ah, there it is) should do the trick. Might sound stupid, but I could imagine when entering airplane mode Android does something similar to
/etc/init.d/networking stop, which has a DNS flush as side-effect.
A very easy solution was supplied by dtumaykin in the comments below: simply switching to airplane-mode and back might already do it (of course with the side-effect of the network going down for a couple of seconds ;) Though it might not work on some devices, it's worth a try: no extra installs, and easily performed even by n00bs.
If anybody tried one of those solutions, confirmation (or the opposite) is surely welcome :)