Others have given information that ordinarily would be accurate for most cases, but there's something unusual here.
What happened with the previous marriage? Was an immigration petition ever filed? If not, why not? If so, what was the result?
The law changed in 2001. Prior to that time, if he was married a US Citizen, he could have adjusted status without leaving the US. The law which allowed it was INA 245(i). If he was the beneficiary of a petition that was filed before April 30, 2001, INA 245(i) may still allow him to adjust status, even if he would now be adjusting status based on a completely different petition.
If he may have been the beneficiary of a petition filed on or before April or 2001, see
http://www.murthy.com/adjsta.html ,
http://www.shusterman.com/245i-faq.html , and/or talk to a good immigration attorney.
Maybe it's a long shot, but adjustment of status, if it's available to him, is probably a much easier route than going abroad, having the visa denied, and getting a waiver.