The problem is that your drawing is tightly tied to your updates, and vice versa. If the game is drawing at 1000 frames per second, then update() is called 1000 times per second, and your terrain is going to scroll by at 1000 tiles per second.
The solution to that problem is to use a timestep to increment your simulation. In this case, say you want your terrain to scroll by at 60 tiles per second. That means you must call update() once every 1/60th of a second, and no more.
You can achieve this by using a timer and a time accumulator. Every time through your main loop, check how long has elapsed since the last time the loop ran. Add that value (generally represented as a floating point number in units of one second) to the accumulator. If the accumulator is greater than or equal to 1/60, subtract 1/60 from the accumulator and call update().
I'm not familiar with the Android timer APIs, but the general pseudocode looks something like:
// initialize time
last_time = GetCurrentTime();
accumulator = 0;
update_speed = 1/60;
while (!quit) {
// calculate elapsed time since last frame
current_time = GetCurrentTime();
elapsed = ConvertToSeconds(current_time - last_time);
// store current time for the next frame
last_time = current_time;
// if the accumulator is full enough, update game and "drain" accumulator
accumulator += elapsed;
if (accumulator >= update_speed) {
update();
accumulator -= elapsed;
}
draw();
}
Of course, this is a very rough and basic way to go about this. Going forward, you'll want to separate the speed the terrain scrolls by from your update time. You might have a character you need to update at 60 frames per second to feel "smooth" while the terrain is moving by at 20 tiles/second still. You can do this by using a "speed" multiplier for your world scrolling, giving it a separate timer/offset/accumulator from the one in your main game loop.
So far as the choppiness you encounter when you slow the game down, that is because you are moving the world one whole tile at a time. You should smoothly scroll the world, which is going to happen at the pixel level (or possible sub-pixel level, depending on what look/feel you're going for).
You'll want to store an offset in your tile data structure. As the update() function runs, simply increase this offset by your desired speed. (e.g. you want the terrain to move at 20 tiles/second, but you want to keep update() running as 60 calls/second for physics and such, so you increment the offset by 20 * update_speed).
You will need to generate one "extra" tile, because as the world moves to the left, you'll see a part of the left-most tile and a part of the right-most tile just coming into the screen.
When the offset reaches or exceeds 1.0, that is when you remove the old tile on the left, generate yet another new tile on the right, and decrement the offset. Something like:
offset += scroll_speed * update_speed;
if (offset >= 1.0) {
offset -= 1.0;
RemoveLeftTile();
AddRightTile();
}
Going down the road, there's a lot more to do and learn with how to get nice smooth animations, accurate timing and timesteps, and so on, but this should be a good start given your current game development skill level. When you're ready to deal with more advanced problems in the world of game timers and updates, there are already many great articles here on GDSE to help you out. :)