I think we solve the problem not by forcing those who are religious to accept gays, or by forcing gay people to accept a different word for the same rights. I think we solve it by acknowledging that marriage should never have had rights, and forcing anyone who wants the rights currently afforded to marriage, gay or straight, to get a civil union. Or hell, if you don't like civil union, call it a taxed co-habitation rights application.
Once the government has no interest in marriage, no one can stop a gay person for getting married if they'd like to. Just like no one can force a very religious community or church to recognize that marriage.