I got my first job at age 16 with no experience - ie I had done some babysitting before, but nothing else.
I would reccommend you go into smaller shops in your area even without them having an 'casuals needed' or whatever sign in the window and ask to speak to the manager and ask if there are any opportunities. Basically this shows your initiative and enthusiasm - the way I see it, if there is someone who actually wants a job there they would be pretty stupid to turn you down.
My story: I live in the lower north shore, and applied for a job at a small french patisserie in Castle Crag - just went in and asked to speak to the manager. There weren't any customers (go at a low business time so that they aren't stressed) and talk to them. Inform them of your relevant skills eg I can speak French which also helped, or anything. I was told to come back for an interview the next week and then was offered a job. The end.
I worked there for a year although I didn't really like the job that much - the experience is important. I would say try and get a contract because I was paid cash in hand which meant they thought they could pay me less because I wouldn't be taxed... dodgy dodgy. But the hours were good - I was in year 11 and worked some afternoons and then sunday mornings. In year 12 it was only sunday mornings so I earned about $50-60 a week. Had I wanted to I could have worked more.
Good luck