1 While both the CELTA and Trinity are recognised, I would say that the CELTA is the industry standard and would be the best if you are going to be travelling around as everyone has heard of it. While you would probably be able to find work without it as you already have teaching qualifications, I would still advise getting it as it opens doors in the better paying places, which can be a bit snotty about non-ESL qualifications.
2 Quite possibly.
3 I know plenty of couples who have done it. You might not walk into jobs on the same day or in the same place, but you should both be able to find work. In a previous incarnation as a DOS, I employed a couple of couples.
The only issue that might come up is your nationality within the EU as EU teachers from Britain and Ireland are legally easier to employ, though many Americans do work there.