Specific to just one early colony, Virginia had laws as early as 1624 requiring attendance at Church of England churches and mandated the use Book of Common Prayer in services, to the dismay of Puritans who preferred their own services and wanted nothing to do with the BCP. Later, in 1660, Governor Sir William Berkeley, who was "bitterly opposed" to both Puritans and Quakers, passed a law fining any ship captain that brought Quakers to the colony. Quakers that did arrive were to be arrested and deported -- and Quakers who ignored the law and were caught three times were imprisonment as felons. source

In addition to /u/Snapshot52's notes on the Ghost Dance, Wounded Knee and the American Indian Religious Freedom Act, I would also include the American Indian boarding schools system, which explicitly aimed at "Christianizing" Native American children. It can be easy to overlook this as political/cultural/social, rather than religious oppression, but that certainly was one of its defining roles.

And I think it is worth remembering that the establishment clause of the First Amendment didn't spring from thin air. It is famously associated with Thomas Jefferson's letter to the Danbury Baptists, whom he wrote after reading of their fear of Connecticut's majority Congregationalists.

Early colonists? Americans were repressing religious freedom a lot more recently than when the first settlers stepped off the boat.

In 1890, a new religious movement began sweeping through Native American communities. Starting with a vision by a holy man named Wovoka, this movement soon became known as the "Ghost Dance." This belief centered around the idea of the removal of the white man from Indian lands and the return of the buffalo to the Plains. In order for this to occur, natives had to participate in a specific dance and song, this being the Ghost Dance.

In 1881, Sitting Bull and his band returned from exile in Canada and settled on a reservation. Both prior to and after his return, reservation conditions were abysmal. Disease, neglect, starvation, and death ran rampant within their boundaries and the U.S. Government cared little for what happened to the Indians, particularly the Sioux. When the Ghost Dance came around, many natives were revitalized. Their hope was renewed and their zeal was rekindled. Unfortunately, the Indian agents and feds saw this movement as a threat. They reported it as being "disturbing and unstoppable" and blamed Sitting Bull as being a major proponent for this perceived danger. The federal government soon outlawed this dance and would punish anybody they found to be associating with the movement. Sitting Bull was later murdered by reservation police that were sent to arrest him.

In 1924, all Native Americans were given American citizenship. However, they did receive all of the same benefits that other American citizens did. It wasn't until the enactment of the 1978 American Indian Religious Freedom Act that tribes were legally allowed to practice their various forms of religion without harassment from the government.

Getting back on track with your question, though, many early colonists did not approve of other religions (including my focus on Native American beliefs). Part of the assimilation process was to have the natives adopt their religion. They were not permitted to practice it. Many of the European colonists did this, the Spanish Missions being a prime example of early assimilation efforts.

To understand the way that religious freedom has evolved in throughout US history, a little context about where it started is helpful. The TLDR of it is that, originally, the US Constitution did not guarantee the universal rights of the citizens, but rather restrained the Federal Government from violating those rights.

Some of the colonies established by settlers in North America in the colonial era where founded by groups seeking a new home in which to live where they could practice their religion without interference and without fear of persecution. The context of this period is a world of Christendom that had been torn asunder by sectarian wars of religion and other religious strife. Puritan and Quaker communities came to the colonies to follow their own religious practices. Note, however, that these were communities seeking the freedom to practice their religion and to live in a society that was governed and organized within the rules and strictures of their religion. This is very different from the idea of individual religious liberty. An individual living in the Massachusetts Bay Colony was not free to decide that they wanted to covert to Catholicism and convince others to do likewise.

Some other colonies did have nominal individual religious freedom, like in Connecticut, Rhode Island, and Pennsylvania. Some leaders were wise enough to believe that faith could not be forced on someone.

Religious beliefs and practices varied from colony to colony, and when the delegates to the constitutional convention convened, much of the concern surrounded the possibility that a Federal Government could be too powerful and could interfere with the individual states internal dealings, including persecute or undermine the local religion, or otherwise force one religion on them. The Constitution constrained the Federal Government such that it could not do anything that Constitution specifically said it could do (this is every new US law needs to be able to fit itself into some part of the Federal Governments constitutional authority) and with the First Amendment it also laid out a number of things that the Federal Government specifically could not do.

However, the First Amendment did not constrain the states, themselves. It wouldn't be until 1868 that the Fourteenth Amendment bound states to uphold the rights of citizens provided for in the Constitution. Notably, the Fourteenth Amendment was one of the Reconstruction Amendments and the Southern States were forced to ratify it as a condition of regaining representation in Congress after the Civil War.

I will say that Clinton is probably somewhat right about the US being associated with religious freedom since the pilgrims, but not because the colonies were a bastion of religious freedom but rather because America was a frontier where if you wanted to be different, you may not find acceptance in the settled lands, but you could always go and find seclusion. In North America you could live where government authority was weak or entirely absent and you didn't have to worry about foreign armies invading to stamp out your heresy.