Hopefully Fring will go legit when the App store is up and running. Also, see:
http://www.icall.com/index.php
Sounds like it is definitely doable, just might have to wait a few months. Skype might not want to upset 3 Mobile though by offering iPhone software too soon.