Sending info from python to avr-c
One option is to parse the string in python and then send some sort of binary format to the microcontroller.  This would be more efficient bandwidth-wise and the MCU code will be much simpler.  The link to the microcontroller would still be serial, but you would not be limited to sending printable characters.  It's quite easy to do open a serial port with pyserial in binary mode and then do port.write(struct.pack(....)) to send binary data down the link.  

In your C code, you can declare a structure and then cast a pointer to the received data to a pointer to the structure and then directly read out the data elements, no parsing required.  

I actually have a bunch of packet processing code that I wrote a few years ago for an AVR project here: https://github.com/alexforencich/xgrid/blob/master/firmware/xmega/xgrid.cpp.  It's not designed to be used with the Arduino environment, but it should be able to run on the 328.  There is a bunch of other stuff in there that's specific to this particular project, but take a look at send_raw_packet, try_read_packet, and try_parse_packet to get a feel for how you can transfer structured binary data over the serial port.  

Update:

Looks like you're looking at the right libraries for sending data to the AVR, but there are still a few things that you should look at.  First, the idea behind binary protocols is to send blocks of binary data which are defined by structs.  For example, you might need to send a point object that has an X and a Y coordinate.  You would define this in C as

struct point {
    int16_t x;
    int16_t y;
};


In C, you can create an instance of the struct, initialize it with the required data, create a pointer to it, and cast it to a char pointer, and send it to the serial port:  

struct point p;
p.x = 1;
p.y = 2;
uart.write((char *)&amp;p, sizeof(point));


Then in python, you would do something like

(x, y) = struct.unpack("hh", ser.read(4))


To go the other way, you can invert the whole process like so:

ser.write(struct.pack("hh", x, y))


And then on your microcontroller:

struct point p;
usart.read((char *)&amp;p, sizeof(point));
x = p.x;
y = p.y;


Now, you will need to do more work than just this to support things like framing and object identification (some sort of packet type field), but this should be enough to get you started.  

I said it before and I will say it again: look at the implementation of try_read_packet here: https://github.com/alexforencich/xgrid/blob/master/firmware/xmega/xgrid.cpp#L257 .  This manages atomically pulling packets out of the UART receive queue in a nonblocking fashion - it will do nothing and return 0 if the whole packet is not in the buffer, otherwise it will read out the packet and parse it.  The packets themselves are built from a fixed identifier byte 0x5A followed by a 2 byte length followed by the payload data.  Well, sortof.  The packets used in that project actually have a bunch of other standard fields, but those first 3 bytes are handled differently in try_read_packet as it has to read them to know how big the packet is, and the rest is handled as payload data.  The implementation of try_read_packet is quite simple.  It drops characters until it sees 0x5A.  Then it uses peek to get the length without dequeueing the bytes.  If the whole packet is available, it reads it into a buffer and passes it to try_parse_packet, which casts the buffer pointer to a structure pointer and reads out the header fields.  The idea is you can call this routine in a loop and process packets as they arrive.  The transmit side is dirt simple, just set all the correct fields in the struct, get a char pointer to it, and pass that off to the UART module for transmission.