I'm not sure how well this wold work as cut vinyl either, and retain their brand integrity. I would assume that the customer would like to have the gradients in the lettering and flames. Red/blue/orange cut vinyl would look horrid.
Someone needs to either provide vectorized artwork or you have to redraw it (for an extra charge - this can sometimes motivate people, lol)
Then, find another local shop who can print/cut the vinyl for you.
I don't see how a shop could make it without a printer & an artist who doesn't know how to redraw something this simple (or understand the answer to your basic question), so I would like to take a guess and say you're a guy with a plotter in his garage?