I would start in the northwest corner of AL near the tri-state borders of MS, TN + AL, not far from Florence and the Shoals area. The Natchez Trace parkway passes through right near there. You will have a relatively flat route the entire distance to the gulf if you go south roughly parallel to the MS-AL state line. There is an official bike route, part of which is in MS and part of which is in AL that takes you to Mobile. From Mobile I'm sure you can find your way home. October would be a good time, when the temps drop down a bit to make it a more comfortable ride.