What you propose is exactly what I'd do: make a while loop that repeatedly reads up until a certain terminator. Let's say, for example, that you define 0 (binary 0) to be your string terminator. Your transmitting Arduino would do something like:
Serial.print("LEFT:100:RIGHT:50"); // the data
Serial.print(0, BYTE); // the terminator.
Then, on the receiving side I'd write a function that captured the data into a string buffer like this:
void GetString(char *buf, int bufsize)
for (i=0; i<bufsize - 1; ++i)
while (Serial.available() == 0); // wait for character to arrive
buf[i] = Serial.read();
if (buf[i] == 0) // is it the terminator byte?
buf[i] = 0; // 0 string terminator just in case
Then, call the function to get a string and parse it using strtok_r():
/* parse buf using technique above */
/* do something with the data */
That seem reasonable?