Coleman received an athletic scholarship to attend the University of Tennessee, where he played for coach Phil Fulmer's Tennessee Volunteers football team from 1997 to 1999. Starting as a freshman in 1997, he played in 35 games, and starting 30 of them, over his three-season college career. As a sophomore, he started all 13 games and led the Volunteers to a Southeastern Conference (SEC) title and a 23–16 victory over the Florida State Seminoles in the Fiesta Bowl) to win the BCS National Championship. For his stellar play during the 1998 season, including going the entire year without allowing a quarterback sack, Coleman was named first-team All-SEC selection and a second-team All-American. He was a first-team All-SEC selection and was recognized as a consensus first-team All-American honors following his 1999 junior year. Coleman decided to enter the NFL Draft after his junior year.
Coleman was drafted in the second round of the 2000 NFL Draft (37th overall) by the Tampa Bay Buccaneers. As a rookie with Tampa Bay in 2000, he appeared in eight games at both offensive guard positions, and averaged about six pancake blocks a game. He moved into the starting lineup in 2001, starting for all 16 games and the Buccaneers' playoff game. Looking to improve further, Coleman started 15 of 16 regular season games in 2002 as well as all three playoff games, which included Super Bowl XXXVII. In that game, the Buccaneers dominated the Oakland Raiders en route to a 48-21 victory and a Super Bowl title. Coleman would start all 32 games over the 2003 and 2004 seasons and continued to cement his reputation as one of the league's best (and most underrated) offensive linemen.
Following the 2004 season, Coleman moved on to the Cleveland Browns and was promptly inserted into the starting lineup for a young Browns team. Over his seven-year career, Coleman has played in 85 games and started 77 of them. Coleman announced his retirement from the league in 2007 after seven years in the league due to bad knees, which not would allow him to pass a physical.
After retirement from professional football, he re-enrolled at the University of Tennessee where he majored in legal studies. He is currently an assistant coach for the Middelton High School Football team.