Immigration has this to say about that 3-month period:
Q17 I heard that my status of residence would not be revoked even if I fail to engage in my intended activity relating to my status of residence for three months because of "justifiable reason." It is true?
A. Your status of residence will not be revoked even if you stay in Japan with one of the statuses of residence as listed in Annexed Table I of Immigration Control Act (Engineer, Skilled Labor, College Student, etc.) and have "justifiable reason" for failing to engage in your intended activity relating with your status of residence for three months. The immigration control authority listens to your opinions when evaluating if or not you have " justifiable reason" on a case-by-case basis. For example, the immigration control authority might not revoke your status of residence in the following cases because you are regarded as having " justifiable reason."
1. After losing your job due to bankruptcy of your employer, you go about getting a job, including actually visiting a company for an interview in order to seek for a new job;
2. After Japanese-language school you have been attended was closed down, you are working on necessary procedures to enter a different Japanese-language school; or
3. You need long-term hospitalization for medical treatment and have no choice but to take a temporary leave from university, but intend to go back to the university after coming out of the hospital.
So, what does this mean? Well, unless you can prove one of the reasons above, you may (I emphasize this word, MAY) run the risk of losing the visa. Bear in mind that nobody is going to come hunting for you on some sort of Minority Report detective. Three months is a long time to be looking for work, and if you are already considering a change, you will have more than that to do your own hunting.
*Can I do some part time job until I found another job, or I just can be employed full time?
I assume you have not worked for a full year yet on that visa status. You can quit and pick up part time work (or continue with your current company and pick up PT work, too), but until you have been here a full year working, you must still have someone to sponsor your work visa. If you are doing nothing except PT work, you have to convince someone (usually the largest contributor to your salary) to help out, and the total PT money you earn needs to be acceptable to immigration.
I'm not 100% of all this, but I can tell you that after the first year, you can essentially "self-sponsor" your visa with just PT work as long as you make a certain amount (undefined by immigration, but somewhere in the range of sustainability, figure 180,000 yen/month or more).
Realize, too, that as of spring 2010, you will need to be on a national health insurance program in order to renew your visa. Not sure if that applies to changing sponsors or not beforehand (i.e., before 2012).
