is there any way to test your icon other than to change it once per week and see if downloads change (meanwhile hoping nothing else changes to confuse the data)?
That sounds like an excellent approach that should work well - similar to how Tim Ferriss named "Four Hour Work Week". (Not a games guy here, but I am an ad/marketing guy in one of my hats)
Do run your ads to statistical significance, though!
Just make a dozen variations, break into groups of three, put each set on it's webpage with a header question "Which sudoko game would you rather play?" Install click tracking via your tool of choice GA/Optimizely/VWO/CrazyEgg/Clicktale. Then head on over to either mechanical turk, usertesting, gorillatesting, or one of the other many services out there. Target your expected demographic and pay for a 5-20 individuals (or whatever volume of people will make you comfortable) to go through each set clicking the one they'd want to play. Take the winner from each set, create a new page with the three winners, select a new group of testers. Take the winner and make it the first one you go with. Then over time you can try switching some in and out of the actual app store. But increase the chances that your first one is your best!
