Hello. Most TEFL courses ask for a degree as the course is so intensive with such a large amount of course work, that a degree gives them proof that you are capabable. However, all courses normally have an alternative way for you to show them that you are capable, this is usually in the form of a telephone interview and an essay. The most important thing if you are looking to work in Europe is that the course you do gives you real teaching experience - you can then take your portfolio of lesson plans, materials, grades etc along to interviews and talk about your experiences of teaching different levels etc. If you are thinking of Spain, think carefully about the location as it is easier for Americans in some cities than others.
Good luck with your adventure!