Try to search for the Nokia N78. It would have been in your budget and contained all the features that you mentioned.
If you can leave out the GPS then you can get the Samsung i450, Nokia 5320, Nokia E51 in that range.
P.S: E51 does not have a stand alone 3.5mm jack, you have to use a converter to use your standard headphones. The converter us very easily available.