The description about this show sounds exactly like the old video game Jet Grind Radio.
Jet Set Radio Futre (xbox): "Similar to the original, it depicts a future Tokyo where freedom of expression is outlawed. You play a character in the GG's, a gang of rollerblading graffiti artists who skate around Tokyo covering up rival gangs' graffiti, knocking over Rokkaku police, and dancing to the eclectic soundtrack. The game uses the cel-shaded style of animation, and has been widely acclaimed for its unique music stylings, detailed art, and fun gameplay."
Edit: In-Game Video Review Video