I spent some time to investigate this problem and found some solution to my specific situation. Except free shipping , there was error "no carriers available" at the fourth step of the checkout. That was caused by the place where the delivery would start - warehouse . When you go to admin/catalog/products you find the tab "warehouse". Connect your product to a warehouse. Than go to Stock -> Warehouses, click edit at the Warehouse you need, fill in all required fields and the main one - CHOSE at least ONE CARRIER in the CARRIERS list. Save changes and the Carrier will appear in the 4th step of the checkout if the customer address is from the same zone with the warehouse.
This also ended the "the always free shipping" problem. P.S. The mentioned Prestashop version is 1.5.6