One mistake many people make is buying a lens without trying it - I will admit that I have fallen foul of this.
I would not recommend a fisheye lens, as it is very specific and you may not use it too often.
When you say you think the Canon 2.8 Fisheye lens is only for more expensive cameras, do you mean that you think it won't fit your camera? Because all of the current lenses (EF and EF-S) will fit the 450D.
If you're looking for ultra wide-angle, you have two real options:
Sigma 10-20mm f/4-5.6 (~£380 new, ~£300 used)
Canon 10-22mm f/3.5-4.5 (~£650 new)
Both of these are amazing lenses - I myself own the Sigma 10-20mm, and I use it on my 450D. It produces sharp photos, and it's incredibly wide! I've almost walked into things looking through the viewfinder because it makes them look so far away when they're right in front of you.
I personally don't think the Canon is worth the extra money if you're just starting out. It produces less distortion at the wide end, but the Sigma is still great. The sigma also comes with a lens hood, whereas the Canon doesn't.
A shot I took last weekend at an event:
A bit of distortion is evident but it's acceptable. When the lens is wider, there can be alot of distortion. The lens focuses quickly and silently. Couldn't ask more from the AF system.
As the previous poster mentioned, try to borrow the lens before using it. Or at least try it out in the shop first to see if you like the feel of it.