Can I use Weedle's "Speed Evolution" attack on my first turn of the game or the turn it comes into play?
Yes. An attack can override the normal rules for evolution.
Source: Unleashed FAQ (2010-05-13), PUI Rules Team (2010-05-13)

Relevant cards

Note: All applicable cards may not be listed below.
HGSS2_32
HGSS2_69