Django: broken migrations
Answering this question:

So the only solution I can think of is exporting the database from the old machine, where it is working, to the new one. Would that work?

Yes, this can work if you are sure that your database is in sync with your models. It is actually the way to go, if you want to be best prepared of updating your production environment.

get a dump from the current production machine
create a new database and load the dump
check whether there are differences between the models and the migration history (this is more reliable with the new Django migrations, South was an external tool and had not all of the possibilities) (e.g. ./manage.py showmigrations (1.10), ./manage.py migrate --list (1.7-1.9 and South)
If you are confident that no migrations have to be run but the listing shows differences then do: ./manage.py migrate --fake

Note, in newer versions you can do ./manage.py migrate and it will report that everything is in order if the models and the migrations are in sync. This can be a sanity check before you deploy onto production.
I am trying to setup a Django app locally in a new machine but migrations seem to be totally broken. They need to be performed in a particular order, which worked in the first machine I set the environment in a couple months ago, but now there are inconsistencies (although I am pretty sure no new migrations were generated).
So the only solution  I can think of is exporting the database from the old machine, where it is working, to the new one. Would that work?
This would not solve the broken migrations issue, but at least I can work on the code till there's a proper soltuion.