Coleman attended Bryan Adams High School, where he was named prep All-American and All-state at running back, after rushing for 1,521 yards as a senior. He was a highly sought after prospect and accepted a football scholarship from the University of Notre Dame in 1987. As a freshman, he recorded 6 carries for 20 yards as a running back and 6 tackles as a defensive back. He also played on special teams as a member of the travel squad. Looking to play at running back, he decided to transfer to the University of Texas in 1988. When the move fell through, he transferred instead to Baylor University. In his redshirt year, he was given an award for excellence as a practice squad player. As a sophomore, he appeared in 11 games, rushing for 368 yards and 3 touchdowns. He left the school at the end of the 1989 season, after not meeting the academics requirements.
Professional career
Coleman played football for the semi-professional team the Dallas Colts, while also working as a lot man at Home Depot from 1991 to 1992. In 1993, he was working loading docks at Marshall Field's, when he signed with the Dallas Texans of the Arena Football League as a part-time job. He was discovered by a Dallas Cowboys trainer instead of a scout, while he was watching a Texans game on television. Because he was bothered by an Achilles tendon injury, he was signed by the Cowboys as an undrafted free agent until August 12. He was waived on August 30, but showed enough potential to be signed to the team's practice squad two days later. On November 17, he was promoted to the active roster to backup both Emmit Smith and Darryl Johnston. His NFL debut was in the infamous Leon Lett Thanksgiving game against the Miami Dolphins, replacing an injured Smith and displaying a punishing running style through a sleet-marred field, while rushing for 57 yards on 10 carries. His efforts were lost around all of the media attention that focused on the ending of the game. He went on to become a Super Bowl Champion, but he developed a substance abuse problem and reported to the next year training camp out of shape and overweight at 256 pounds. He was cut on September 6, 1994. He was signed on September 11. He was not re-signed after the season. On July 21, 1995, he was signed as a free agent by the Atlanta Falcons. He was released on August 27. He was signed again on February 1, 1996. He was cut on August 19, only to be re-signed on September 4. He was released on September 24 to make room for quarterbackBrowning Nagle. In 1997, he was one of the Arena Football League best rushers with 246 yards, while playing for the Milwaukee Mustangs. The next year, he was suspended by the league for undisclosed reasons. He returned in 1999 and led the Mustangs with 138 rushing yards and 4 rushing touchdowns. He helped the Grand Rapids Rampage win the ArenaBowl XV in 2001.
