I supposed that getting to Cuba by flying from neighboring countries will be much cheaper than the same from Europe, but I have realized that fly prices from Cancun or Miami are very expensive (about $500, that's a 20-30% less than from Europe). And even from other islands there is a high fee to pay. Now I'm looking for alternatives, other cities where I can fly cheaper or, even, ferries, cargo or cruisers which could me take to Cuba for less money. What's the cheapest (and legal) way to get to Cuba from other country?
Since you mention that you are open to getting to Cuba not necessarily directly from Europe but through a intermediate destination, my recommendation would be to consider one of two Canadian travel hubs: Montreal and Toronto.
I recommend these because destinations in and around where Cuba are the main tourist places for Canadians for a big chunk of the year.
You will occasionally find some ridiculously cheap fares through one or more of these methods:
All of the above methods usually require patience to be able to find the cheapest fares but then again, it is something to get started with :)