What is the meaning of 'come off' here?
"came off" here can be read basically as "came directly from". They've come directly from a working duty that made them all dress a certain way. So that's why they are dressed like that.
"off" has a sense of "getting away or released from". For instance, there is the expression "getting off work". You might ask "when do you get off work?" meaning "what time are you released from the duty of being at your job?"
Is 'work' an adjective?
It's used to describe the kind of gang in this case. It is talking about prisoners who have been taken somewhere and made to do labor. For instance digging ditches or cleaning up trash by the highway, perhaps cuffed together and supervised by armed guards. It's a historical thing (mostly):
The usual expressions would be "work crew" and "chain gang", but this has mixed it as "work gang". Which may or may not have been common wording at the time.