Yes, you can root basil in regular garden potting soil, either rich soil from the garden or peat based mixes. The only difference really is that you don't get the feedback of being able to see the roots forming. To root in soil you do the same process as in water, so since normally it is very easy to root basil cuttings in water, the first thing is to figure out what might be wrong with the process.
Cuttings need to be fairly soft; basil can go woody and the harder the tissue the less they want to form roots. Also cut just below a node so you don't have non-rooting tissue to go mouldy. Basil likes to be warm so choose a comfortable location for it in good light. Investigate the quality of your water - it may contain minerals in solution that prevent the roots from forming. A natural source such as rain or well water is sometimes better than a municipal supply. Also the water needs to be aerated to provide sub-surface air to the roots. You can achieve this by changing the water regularly or bubbling air through it.