"In the mid-1650s, the small Jewish community living in lower Manhattan petitioned Dutch governor Peter Stuyvesant for the right to build a synagogue, and they were turned down. In 1657, when Stuyvesant also prohibited Quakers from holding meetings, a group of non-Quakers in Queens signed the Flushing Remonstrance, a petition in defense of the right of Quakers and others to freely practice their religion. It was perhaps the first formal political petition for religious freedom in the American colonies, and the organizer was thrown in jail and then banished from New Amsterdam.
In the 1700s, even as religious freedom took hold in America, Catholics in New York were effectively prohibited from practicing their religion, and priests could be arrested. Largely as a result, the first Catholic parish in New York City was not established until the 1780s, St. Peter's on Barclay Street, which still stands just one block north of the World Trade Center site, and one block south of the proposed mosque and community center."
I know of at least one "formal political petition for religious freedom" in the American colonies before this 1657 event. In 1634-35, the town of Salem lodged a formal protest with the General Court of Massachusetts in Boston which demanded that they oust Roger Williams from the pulpit for his heresies. Eventually, under pressure from Boston involving some land deals, Salem relented and Williams left to found the colony of Rhode Island. Hopefully the supporters of the Cordoba Mosque initiative don't similarly buckle under pressure.
Scott Kuhagen has a great review of the issue here.
What are readers' fondest moments in the promotion of religious liberty in American history?