Actually I have the solution for you that helps to set visibility status to 4 (Catalog, Search).
You can do it using the application called Store Manager in 2 ways - by import or using built-in it tool called Multi-editor.
Here is a free 14-days trial of the application - http://www.magentocommerce.com/magento-connect/store-manager-for-magento.html
It is desktop one, so you can do all the changes locally.
So you can change visibility status via import - you need to update this column without having to re-import all data. You need only column with SKu for identification and column with visibility status with numbers 4 (it stands for Catalog, Search).
Other option - you can change visibility status via Multi Editor of Store Manager. All you need is to choose products - right-click, choose Product Multi Editor and for Visibility change in drop-down - Catalog, Search. But note, it can be done within one attribute set only. So you can beforehand filter the products by attribute sets.
Please, let me know if it was helpful.