The laws pertaining to who can solemnize a marriage vary considerably from state to state. Most of our marriage laws were taken from the legal tradition of England, where were two ways a couple could get married, either in a religious ceremony or under the common law. Religious marriages are what we think of today, going to a clergy member and having him or her join the couple in marriage in accordance with that clergy member’s religious tradition. However, religious marriages were not required. Under English common law, if a man and woman lived together as husband and wife, holding themselves out to the public as such, then they would be considered to be such under the law, despite the fact that their marriage had not been solemnized in any ceremony or before any religious or civil official.
All states have law specifying who is entitled to perfom marriage ceremonies. New York’s laws on this subject are found in Article 3 of the Domestic Relations Law, http://www.assembly.state.ny.us/cgi-bin/claws?law=29&art=4 . All states recognize that clergy members may solemnize a marriage, though some require the clergy to be registered before performing marriages and some do not. (In New York, clergy that marry in New York City must be registered but those performing marriages elsewhere in the state do not.) Because the Establishment Clause of the First Amendment of the U.S. Constitution restricts the government from interfering with peoples’ religious observences, most state statues are written and interpreted to permit marriages to be performed by almost any recognized religious leader (i.e. your rabbi, priest, minister, etc. of choice). A number, such as New York also specify that a marriage in a Quaker ceremony is also valid (because Quakers do not have religious leaders as such, though they do have wedding ceremonies in their congregations). To the extent that other religions don’t have recognized leaders (see the comment on Imam’s above), I’m pretty sure that under the Establishment Clause a wedding performed under that religion’s tradition would be valid.
However, the extent to which states permit civil officials to solemnize marriages varies pretty widely. New York is pretty restrictive, limiting it to mayors, county executives, judges, and a few other officials (A special provision is made for the city clerks that perform marriages in City Hall in New York). Other states, as mentioned above, allow very minor officials such as notaries public to perform weddings. A number of states also recognize recognize common law marriages in which no officiant is required, though marriage licenses may still be necessary. (Some years ago, in a widely publicized case, the ex-girlfriend of actor William Hurt sued him for alimony, claiming they became husband and wife during that during the time they lived together in North Carolina, a state that recognizes common law marriages. The courts rejected her claims.) When the media refers to someone as a “common law wife,” they are usually improperly referring to a couple that is living together unmarried, rather than to an actual common law marriage, which is legally as valid and binding (if entered into in a jurisdiction where it is permitted) as a religious or civil ceremonial marriage.
Because some states are quite liberal in who they permit to perform a marriage (even to the extent of allowing common-law marriages which require no one but the couple and perhaps some witnesses), they may be liberal in allowing marriages by ULC “ministers.” Other states are more restrictive and may have more problems with ULC “ministers.” In any event, I’d have a lawyer check state law (usually there are court cases) pretty carefully before entering into a marriage before a ULC minister.