Personally I think we should sign someone proven in the Premier League (IF Kolo goes), my choices would be
Hangeland - Cheap, proven and solid.
Jagielka - Good player, can play RB as well, proven partnership with Lescott. Could get fairly cheap. (Best option IMO)
Dunne - Mainly for sentimental reasons but he could definitely do a job as 3rd/4th choice CB.
Coloccini - Expensive but a very good CB, would provide serious competition with Lescott. Add to the Argentinians.
Shawcross - Good CB and brave. No doubt Stoke would demand some inflated price but again, for 3rd choice he would be alright.
Or if we are willing to splash the cash then surely Martinez is the best option.