R. 792

Curious what would be the lowest level modifier and monster entry for an outsider (Possibly an Aberation) with the following traits;
Flight
2 natural attacks with reach
An option to advance the creature to 4 natural attacks
And the inate ability to teleprt at will like a jaunty fellow.

Purpose: I am setting up a skype campaign which will be run episodicly. Set in the modern day where the D&D pantheon has been asleep for a few millenia. One of them is about to wake up, and this creature will be the PC's first encounter with a sentient being that isn't a human. As such I plan on playing up the "WTF" factor as much as possible during the encounter. The reason I ask for as low a level modifier as possible is so that later on the creature type can return and mix things up with class levels.