Hi, I lived and worked (well: taught TEFL!) in Valencia during the 90's. As an Irish citizen paperwork wasn't really a problem (in the end most of my work was in the "black economy" anyway!). As you will already know not being an EU national does complicate things but as far as I know the employment situation in Valencia is fairly buoyant and you should be able to pick something up. It is significantly cheaper city than Madrid or Barcelona so that helps too.

I knew some US nationals who had a few academy hours and also did some translations. There is an English book shop (can't remmebr the address) with a noticeboard for ads. The "chain" such as Opening and Wall St have hit Valencia and seem to accomodate north Americans easily enough but I have heard some dodogy reports from employees. There are lots of small academies around the city where red tape might not be so important and of course you can always try to get private classes.

I couldn't recommend you the names of any spcific schools, but really there isn't a lot you can do until you get there. I guess you know the routine: get loads of CVs photocopied and do the rounds of the schools. Photos would help as they get a number of callers.