Do I need to connect all vcc/gnd pins on the avr?
Yes it allows the chip to frame bonding to take the current specified in the spec.
Does this requires it to run on 16mhz crystal
No but the timing will be out on sevral things like millis() and the serial ports unless you change the files to compensate. Search for that here there have been many examples of changing the clock speed.
Do I need a 3.3V regulator
Yes
which one can I use,
any actually. http://uk.farnell.com/jsp/search/browse.jsp;jsessionid=4WPZYFCLXPQPWCQLCIQJKBQ?N=500006+1002567+383057&Ntk=gensearch_001&Ntt=voltage+regulator&Ntx=&_requestid=428670
Take your pick
how big should the cap be for this.
I would use about 1uF but look at the spec of the voltage regulator for the recommended value, it changes with the regulator. If it is too small it could oscillate.
Is it possible to drive the servos and meassure servo current with the same pin
No. To measure current you have to break the drive line and insert a resistor. Then measure the voltage drop across the resistor.