thing with cheap and cheerful, is it limits you so much, and really, If you want to invest in Photography later, the more you spend up front, often gets you more later on. If you want to take decent skating pics, you want something that is fast (fast shutter speed, to capture movement without blurring). Any digital camera SLR or otherwise will take adequate snaps, but if you want better quality pictures, then better quality kit will make this easier. A fish eye lens looks cool, but is a bot over used in skate mags. The problem is, its a very specialist image it creates and is useless for pretty much everything else. A good wide angle lens will serve you better, and as noted above, you can do a fisheye effect later on with editing software (which in my opinion is a better way to go about it!). The ability to zoom will let you take shots from further away, which stops you getting hit, but can leave your pictures looking a bit like you are watching the action rather than being "in it" If you know what i mean? Also, as another tricky thought, consider getting a fast lens (as in low F number), which will enable you to focus on a skater whilst blurring the background (making them look fast and helping the viewer to focus soley on the skater) and also enable you to take photos in environments with less light without needing a flash.
As for a cheap set up, maybe pick up a cheap SLR body (I'm a Nikon man, but any will do) and get a 50mm F1.8 lens to start you off (from £100 new, less
second hand) I'm not sure where abouts you live, but my local camera shop has a few 35-70mm zooms with F3.3 which would work quite well and can be had for about £50.
As an after thought, if you can get a camera that shoots movies, this is an easy way to get "the shot". I used to take a lot of BMX pictures, but found that the rider would be looking the wrong way, or I'd release the shutter at just the wrong moment. A short film, maybe 5 seconds wold catch the whole move then I could flick through, frame by frame and find the perfect shot. Quality suffers though.
Hope some of that helps! Remember, its the photographer, not the camera!