We've also heard you can pretty much just show up and find a job, but how does the visa situation work there?
Not to burst your dream bubble but you heard wrong.
That MAY have been the case in past years but the world economic situation has affected China and visa policies make it much more difficult to do that.
Some employers can change your visa without you having to leave but that's never a given. At the risk of getting my tight ass chewed out by Uncle Yu I won't suggest you attempt to work on anything other than a real working visa. Keep in mind that not every employer or school can get you a real working visa and some may allow you to teach/work on a tourist visa.
I have always had a Z visa and the school I work at is legit but there is one fellow working here on a tourist visa but that ain't my business...
Finding 4 month work is not easy at all. Your option is committing to a 6 month or longer contract and them requesting to leave at the 4 month mark. Issues with that are usually you will lose some salary, but most that opt to do that will use the family illness excuse or just quit the day after payday. It's a matter of karma.