Robert_Charlton - 10:45 pm on Mar 13, 2013 (gmt 0)
...if i add no-follow on those then i will have no hope to rank
Essentially, you are saying that you're depending on these client footer links to rank you, and that's essentially been your linking strategy.
Google at this point is looking for freely given editorial links from trusted, relevant sites, and that's what you need to build.
I recommend you take the advice given above and ask your clients to "nofollow" those footer links on their sites. Yes, you will lose the ranking effects of those links (assuming, ie, that there is any left to lose). What you gain by the nofollows, though, is avoiding any appearance of manipulating PageRank.
(An alternative approach, I suppose, might be to leave those links as they are and get editorial links to put those links in a minority. IMO, it's much to late to take this latter approach. You certainly won't be able to build enough editorial links naturally, and Google will surely spot any artificial approach for what it is.)