Actually, you need to establish a merchant account and a payment gateway account. The merchant account is with the bank who facilitates your transactions to the card issuing banks for approval. The payment gateway acts like a credit card terminal as it connects your website to your merchant account provider.
To automatically bill your customers every month you can either build your own subscription service (bad idea as you will have to store credit card information which opens a big can of worms, namely PCI compliance issues) or use pre-existing services like Authorize.Net's Automated Recurring Billing service which handles the subscriptions for you. Options like trial periods are usually built into services like that.
If you're going to accept a variety of currencies then your options take a huge plunge. Most US processors and payment gateways only accept payments in US Dollars. International transactions also make your account high risk which will greatly reduce the number of providers who will accept you and offer you competitive rates.
Alternative solutions would be to use Paypal or any other third party payment provider. You lose some of the flexibility and control that you would have with a true merchant account with a payment gateway but accepting payments in different currencies and international orders become less problematic.