My recommendation would be to use OSM tools for QGIS which you can download as a plugin. OSM tools was created by Nils Rode and is an adaptation of the OSMroute plugin which uses the OpenRouteService API.
Simply download the plugin and request an API key, once you have this you simply use the routing tab (the other tab is for accessibility e.g. isochrones). You can either pick a coordinate from the map or use point shapefiles for your start and end locations.
I believe it limits you to 40 routes per minute and 500 a day, so you may have to split your dataset in two.
If you are comfortable using PostGIS then the pgRouting is a great extension which can be run behind QGIS and then brought in. This has a wide array of functionality. There is a plugin for QGIS but I believe it is fairly basic at the moment.