Its only possible when you get the permission from the immigration. (which you can't get for the first 3 month of school)
After that it's all up to you, and your Japanese language skill. (or rather communication in Japanese skill)
Kind of jobs? Every part-time job is possible (non-adult related).
For me I went from Izakaya -> 100yen shop -> Construction work (haken) -> misc job like operating a XRay machine in haneda Airport for the Japan Postal (haken too)
Almost got a supermarket job too in there. bleh.
try here. I got my first izakaya job from here too.
try the 日本語力少々でも可 section.
currently there's nothing there, It should be filled up anytime soon considering the bounenkai season is almost here. So always check there.
When you have enough confidence in your Japanese comm skill. try choosing from the other place. Those place might not have any foreigners working in that place. But they don't mind having one.
What I love about that place is the employer will call you not the other way around to set the interview.