The only true way to make tenderized deep fried battered gizzards is to steam them first before batter frying. Boiling only partially tenderizes and gives them an unpleasant texture. I added full recipe below. Nothing is as good as battered tender gizzards, you should fry some chicken livers with them.
UPDATE:
Sorry I didn't give full directions, the question was asked how to tenderize deep fried gizzards? My answer was (Steam them)
Someone asked recipe and cook times, So I will update this response.
Best batter for these is called Mies flour batter, I order mine from a company in Wisconsin. It's the best gizzard batter with browning agents and flavor enhancers, they sell this batter in bulk normally or to restaurants, but if you ask special they sold to me by the case.
Cooking and prep to fry 3-4 wet lbs gizzards:
Thaw the gizzards, then marinate them (this marinade will be washed off, no worries, you won't taste it). Take 2 cups of vinegar and 1 cup tomato juice and add 1/2 teaspoon Paprika and 1/2 teaspoon garlic powder then toss a few bay leaves into the ziplock bag with the marinade and refrigerate 30 hours or more. The vinegar and tomato juice break down the toughness, and the bay leaves take out the unwanted gamey flavors.
Strain the gizzards and rinse with cold water, and place in your household steamer (if you have one, if not get one, they're awesome to tenderize anything). Steam 15-35 minutes depending on your steamer, and rinse with cold water in your strainer again as soon as tender, test one every 15 minutes for perfection.
Add a prebatter in a bowl with a cup of water and 1/4 cup or so of Mies batter with some more Paprika, just thick enough to make the gizzards really sticky before you dip into the dry batter or shake in a bag of drye Mies, while you get 2 pots of oil heated to 400 degrees. You can improvise a strong dark ale beer instead of water if you prefer, (never ever make a batter with light beer, as it will give only an aluminum like taste, If you only have light beer to cook with, your best off using water instead.
When oil is ready, place gizzards in a lidded bucket or bag with your dry batter only after your oil has reached 400 degrees, shake into the batter, and drop as many as your oil pot fits without cramming them in to thick, give them room to cook. Let cook 3-4 minutes only in the 1st pot, then pull out and switch them quickly into the other pot that's still 400 degrees because the 1st pot dropped temperature from adding the cool gizzards in. Now in your second pot that you moved the gizzards to brown them fast, cook only 5 more minutes or until light golden brown because they are already fully cooked in the steamer. Don't overcook, these need to fry in 400 degrees to brown fast. Pull them and dump them out on fresh slices of bread to sop up the oil, and dip them in BBQ sauce and or your favorite hot sauce.
Now you have mastered perfect delicious deep fried tender melt in your mouth crispy deep fried gizzards. If you have a pressure fryer even better, but make do with what you have. Most people will not believe they were gizzards after they taste how tender and delicious. They will argue that its the best chicken nuggets they ever had, saying no way these are gizzards -- if you cooked them correctly! If oil temp is too low, and you overcook before browning, they will be chewy.
Also you should choose a good liquid creamy Shortening or lard, Beef lard from your local meet locker will make the best, or partially hydrogenated liquid shortening or partial hydrogenated soybean oil is the best if you mix with the lard. It's dirt cheap and creates the best homemade lard mix creamy liquid shortening. It will make any batter taste good and make the best french fries you will ever dream of. That oil will even prevent soggy batter, you can put your chicken leftovers in fridge and they will still be crispy the next day. Even a mix of beef lard and partially hydrogenated oil.