Things to think about here
1) unless you froze the whole carboy the yeast are fine. Only the yeast caught in the ice crystals will be dead. The thing behind this is the formation of ice causes the water molecules to expand and bread the cells walls killing the yeast.
2) the yeast are going to be extremely sluggish at bottle conditioning this is why people sometimes add ale yeast or krausen. The fresh yeast has not fallend from suspension and gone to sleep so they will quickly do the carbonation for you. The amount of sugar to be processed by the yeast during bottle conditioning is so small that adding ale yeast will not effect the flavor significantly. The process is to just boil your sugar as per normal, cool it and while it it cooling rehydrate your yeast, add your beer to the bottling bucket on top of the sugar and then add your rehydrated ale yeast. I would not add the yeast dry or rehydrated straight to the sugar solution as it is very concentrated and could harm the yeast.
3) If you are worried about using ale yeast then research krausening this is making a small batch of beer (some people make extra wort and freeze it for later use) add yeast and waiting until it is at high krasen, then taking a SG reading and calculating how much sugar is in the small batch and and add that to the bottling bucket along with the main batch of beer. It is complicated but it is the process used by traditional bottle conditioned german beers. There are some good sites that explain this process with formulas for SG of the beer and SG of the krasuen solution and volumes etc etc and this will work out how much to add.
Good luck
Clem