To be direct, your budget is a bit low for a DSLR and lens. But with landscape photography you don't need some of the bells and whistles of the newer models so a used Canon 300 or 350 would do nicely for the body.
For a lens ... don't skimp. A lens will outlive a digital camera every time. My favorite for landscape use is the Tokina 12-24mm F/4. It is a heavy duty, well built lens with very little distortion even at the 12mm position and great color. I use it on a 1.6x crop body (the Canon 20D) and love the results.
The 1.6x bodies (Canon 300,350,10,20) give this lens a practical focal length of 17-38mm - great for most landscape work.
The following is a link to an unedited full size photo shot with this lens at 12mm - the subject was the side yard of the chapel at Duke University in Durham, North Carolina. Warning: Even though it is in jpeg format, it is almost 4 meg in size!
http://jbs-blog.com/images/offsite/2005-10-05-2311.JPG