You will need a map file somewhere on disk, but you can save copies of it. What you would do is open an MXD with arcpy.mapping.MapDocument, then a layer file with arcpy.mapping.Layer, use layer.replaceDataSource to make it point to the shapefile, then use arcpy.mapping.AddLayer to add the layer which now points to the shapefile to the map document. You would continue until you've added all your layers and then call saveACopy on the MapDocument object to produce your new MXD with all your data sources.
