I understand that operators blocked any Skype over the data connections, but is there an alternative that works on the WiFi network?
Update: I am using a HTC/Tmobile G1 phone, in the US. However, I am not connected to any carrier, as I use it (here) as a PDA over WiFi and not as a phone.
Skype for Android has a couple versions. Most are WiFi-only, so you would be able to use them no problem except that the G1 is not in Skype's list of supported devices, so you won't find it in the Market. Looks like it's Verizon-exclusive. The newest version won't run on your phone even if you grab it pseudo-legally; I'm not sure about older versions.
Skype's API agreement also prohibits other apps from making Skype calls, as far as I'm aware. Fring used to support Skype, for example, but had to remove that feature due to threats from Skype.
What country are you in? Skype have only got an exclusive deal with Verizon in the US, outside the US it isn't restricted to any carrier AFAIK.
If you go to an international version of the Skype site, like http://www.skype.com/intl/en/get-skype/on-your-mobile/download/skype-for-android there's a different Skype app that will work on any Android 2.1 phone (even if you manage to download it in the US, it may do further checks to see if you're in the US or not once installed).
Also if you search in the Android Market from a non-US phone (that is running at least Android 2.1) you should be able to find this official Skype app.
See here for more on the differences between the Skype apps.
