Arduino project feasibility

It's perfectly doable. As Chris Stratton puts it, it's all about implementing non-blocking serial communication:

• whenever you receive a character, you store it in a buffer
• whenever you have a complete command in the buffer, you process it and reset the buffer

For a line-oriented protocol, it may look something like:

/* Process incoming characters if any. */
while (Serial.available()) {
    static char buffer[BUF_LENGTH];  // incoming command
    static int length = 0;           // command length

    int data = Serial.read();
    if (data == '\r') {              // complete command
        buffer[length] = '\0';       // terminate the string
        if (length)
            exec_command(buffer);    // process
        length = 0;                  // reset buffer
    }
    else if (length < BUF_LENGTH - 1)
        buffer[length++] = data;     // buffer incoming character
}

For a more complete example, you may want to take a look at this simple Arduino command line interpreter. You connect a terminal emulator to the Arduino at 9600/8N1, type the "help" command and it displays:

mode <pin> <mode>: pinMode()
read <pin>: digitalRead()
aread <pin>: analogRead()
write <pin> <value>: digitalWrite()
awrite <pin> <value>: analogWrite()
echo <value>: set echo off (0) or on (1)

You can use it as a template, replace existing commands or add new ones (the interpreter is just a long if ... else if ...) and – since it's all non-blocking – add whatever you want to loop().