don't be disheartened annelie. you have a certification and you studied in UK that's an advantage. Although English is the co-official language of my country, Japanese seems not to know that and I don't have any certifications, cause I hate taking them
Try applying for YMCA, I know for a fact that they accept applicants with proper teaching background than just accent.You can also try GABA.
goodluck