Coyne was born in Pittsburgh, Pennsylvania, United States, the son of Thomas Coyne and Dolores "Dolly" Jackson. The fifth of six children, Coyne moved with his family from Pittsburgh's Troy Hill neighborhood to Oklahoma in early 1961. Coyne grew up in Oklahoma City. Coyne preferred listening to music and playing pickup football. He, his sister, and his brothers dubbed themselves "The Fearless Freaks" for their brutal backyard football games. Tommy Coyne, Coyne's older brother, described the games as a "semi-civilized gang fight."
In 1977, while in high school, Coyne began working as a fry cook for a Long John Silver's restaurant in Oklahoma City. During his second year of employment, there was a rash of robberies in Oklahoma City. The restaurant was robbed and Coyne and other employees were held at gunpoint and forced to lie on the ground. Coyne was certain he was going to die. The assistant manager couldn't open the restaurant's safe, however, and the robbers eventually fled the scene. Coyne believes "this is really how you die...one minute you're just cooking up someone's order of french fries and the next minute you're laying on the floor and they blow your brains out. There's no music, there's no significance, it's just random." Coyne continued working at Long John Silver's until 1990.