In light of the controversy surrounding attempts to redefine marriage to include homosexual couples, one of the more radical solution would be to exclude the state from marriages altogether and remand the whole business of matrimony back to religious communities.
This is the state of affairs in Egypt, where civil ceremonies are invalid and marriage is the sole purview of the Coptic Orthodox Church. The civil authority, however, recently attempted to force the church to permit a divorce and remarriage, defying a constitutional court ruling holding marriage to be fully within religious jurisdiction. The conflict is yet unresolved, but exposes the likelihood that political-religious disputes would accompany such a scenario anywhere in the world.
Marriage is one of those delicate institutions which fall well within both the religious and secular spheres. A sacrament of the Church, it is also a foundation of society and law. Even if the state were merely to recognize religious unions, it would be necessary to regulate the requirements of such unions - i.e., recognized religious authorities, non-polygamist unions, consenting adults (no minors) and, again, homosexuality. If a solution is to be found, it is not entirely in this recourse.