Unfortunately, this question cannot be answered in its full generality. The majority of payment cards in the EU are offered only by banks and only to citizens of certain countries. Also, except for prepaid credit cards, a bank has to trust you to some extend in order to issue you a payment card. So without some credit history in a bank's country, this is rather difficult. There are some additional obstacles:
- With a customer abroad, a bank may need to take care of additional legal questions (such as issuing an interest report for your tax office).
- Mailing cards and letters abroad costs additional postage
So most banks from abroad will deny your application. Some state that they require citizenship or residence in a certain country upfront (e.g., the Aegean Airlines credit card allows you to collect miles, but you need a Greek tax ID), others are not so open about it (see here for reports in German on changes in the way in which the DKB bank handles foreign customers. They offers fee-free cash withdrawal worldwide with a Visa card ... but apparently nowadays only to people living in Germany, with some exceptions such as Germans living in the USA). British banks are known for requiring some kind of "recommendation letter" (such as a letter from a university for students or an proof of employment in the UK) for foreigners in order to allow opening a bank account with them, which in turn is needed to get a payment card.
Your best bet is probably to find a bank in Malta that gives you excellent conditions on some widely used payment card.