Removing Index.php from url

I have a number of wordpress sites using different WP versions right up to the current 3.5.1. Most of them use the PATHINFO permalink structure (default from WP) which I don’t want. I want to remove all instances of index.php from my urls. I have tried many different variations in .htaccess files, put in my custom structure etc., changing my .htaccess file permissions and nothing seems to work. The index.php will not remove from the “permalinks’ setting in the admin panel of WP, yet the urls look correct from the admin but when I publish I get the ERROR 404 page. Please help as none of my sites are being found on the internet partly due to this index.php reason. I’ve spent so many hours trawling though fourms and I have tried many different solutions but none work. HELP!