That is a really nice research you have done! Thanks for all the info.
I'm experiencing the same problem. I found some other posts complaining about it as well.
Recently I started developing a new game with 1.1 Ligdx (maven project). It's box2d based. There are boxes flying around being dragged to the center of the screen, one texture in assets. I tested it on 3 devices. Samsung Advanced with 2.3.6 Android and 2 no-name tablets with 4.1.1. Android. Here are my observations and some data from USB debugging:
1. There are small hiccups occurring every once and then on all 3 devices.
2. The interesting thing is one major jerk that seems to happen deterministicly at 355th render() call! The drop is from 61 to 53 frames. There is no gc in the process at this moment. I'm also doing all 'new' initialization and Array 'inflating' before rendering, so there is nothing being allocated. I looked at full logcat and there is nothing suspicious, either. I checked my render loop iteration in millis and there is no significant difference for 61 and 53 frames. It seems the code runs the same but the drop occurs. I tried reducing FPS to 50 via Thread.sleep(). Naively I thought the 10 FPS buffer would take care of FPS drop cases but this time it droped to 43 FPS

. I though the issue was related to box2d. I commented out world.step() and made the boxes fly without physics. Same result for hiccups.
3. This point is less important but for my Samsung with 2.3.6 Android the game sometimes starts and runs at 61 FPS (except for the major drop and 1-2 frame fluctuations) and sometimes starts and stays at around 25 FPS for no particular reason. I profiled both cases and looked at time per call. It is not the entire application that runs slower. Major differences are for box2d.step() and rendering calls. The rest of the methods exectute roughly at the same speed for 25 FPS and 61 FPS.
I have no idea where the hiccups for point 1. and 2. come from. Not sure if it's Ligbdx, Java or the Android itself. Desktop runs smoothly.
Anybody checked if the problem occurs with other game frameworks as well?Libgdx devs, I can share my game code with you if you would like to take a look at the cases I described.