Kinko's will do it -- www.kinkos.net.au shows a few locations in Melbourne CBD.
They don't seem particularly good at it, though. I went to them twice, and both times the mat ended up with creases in it. OTOH they charged me half-price, so I'm not complaining.
