If you are a citizen of an EU country, you don't need a visa. However, the job market in Europe is incredibly competitive and so any black mark on your CV can make it much more difficult to find jobs. The only way past that is to do a CELTA or Trinity, try to get a B or A, then get teaching experience in the UK (e.g. in a summer school) before you move abroad.
Portugal is not a common first job destination for some reason. Spain and Eastern Europe seem to be easier, but for Spain speaking the language really helps