Lenses sell for different amounts in different parts of the world. But, to stretch your budget you might want to buy used.
Here in the U.S. it would be easy to pick up a used 28-135 IS for $200 and a used Tokina 12-24 for $400. I don't know if they are similarly priced in your part of the world, if they would fit your budget. However, those two lenses would make for a pretty comprehensive travel kit. Using them on a crop camera such as your 1000D, they actually cover a wider range of focal lengths than most film shooters ever owned in their lifetimes: ultra wide to moderate tele.
The 28-135 has fast USM focus, is quite close focusing, and has pretty good IS. Image quality is good... it rivals the far more expensive 24-105L (the L is better built and sealed, has a little better IS). If the close-focus ability of the 28-135 isn't enough (it's X0.19 or about 1:5, one fifth life size natively), it can be used with macro extension tubes to make it even closer focusing.
An altearnative is the EF-S 18-135 IS. This is now more frequently offered as a kit lens with 60D (or a step up kit lens with any of the xxxD series cameras). It tends to sell for more like $300 in the US and it doesn't have USM focus. The latest version has STM focus, which is better than micro motor, but probably not quite as good as USM. It's also EF-S or crop only. It has reasonably good IS.
The Tokina 12-24 has far less flare and a much wider range of focal lengths than it's more expensive 11-16 sibling.... Also, it's f4... while the 11-16 is f2.8... but most people don't need to use large apertures very often (or at all) with wide angle lenses, anyway. The Canon 10-22mm might be an even better lens for image quality (it's unusually flare resistant)... but likely over your budget. The Tokina seem better built than the Canon (they feel "L-like"). SIgma actually offers a couple different 10-20mm... a cheaper one with a variable aperture and a more expensive one with non-variable aperture. I'm only familiar with the older variable aperture model, didn't find it as good as the Tokina or Canon lenses.
I consider the Canon 28-135 and Tokina 12-24 two of the best bargains out there when bought lightly used. The 28-135 is actually an old film lens, so has been around for quite a while. There are a lot of them on the used market (which is why used ones are discounted about 50% off the price new), it was frequently sold as a kit lens with 40D and 50D (though it's better made than most kit lenses). The Tokina has been around for less time, but there are still plenty of them around on the used market.
With some luck and careful buying, you might have enough left for a small flash or a 50/1.8. The "thify fifty" is the least expensive lens Canon makes, sells new for just over $100 here in the U.S. and can be found for less used. It's about as cheaply made as possible... But it's capable of decent images and it might be nice to have a larger aperture lens for portraits. This short tele (on a crop camera) is small and light, too. Might not need a lens hood with it, either, because the front element is somewhat recessed.
The built-in flash on your camera is pretty wimpy.... and in the worst possible place for redeye and ugly shadows. Instead of a larger aperture lens, you might consider a compact flash. Canon 270EX is small, highly automated and easy to use, but more powerful and it doesn't rely on (and drain!) the camera's rechargeable battery. There are also the earlier 220EX and 240EX, which might serve nicely for travel. If possible, I would recommend putting the flash on a bracket to move it farther away from the lens axis. There are cheap, generic flash brackets on eBay and elsewhere. Some fold nicely for travel. If using a bracket, you also need an off-camera shoe cord to connect the flash to the camera... Canon offers OCSC, but there are far cheaper clones on eBay and elsewhere, that work just fine. Some of these flashes can be found for $100 US or less.
To me, New Zealand means lots of scenic opportunities... not a lot of call for longer focal lengths. However, if you feel you need a lens with more reach, the 55-250 IS is an inexpensive option that's got good image quality. It's frequently offered as a kit lens, is widely available for $200 or less in the US. It is not a USM lens, so don't expect top focus performance. It's reasonably compact for travel. It also can be used with macro extension tubes for close-ups.
For inexpensive macro extension tubes, I'd recommend Zeikos or Opteka. Those are available for around $75-80 US new. Just be sure they are the later versions that are compatible with EF-S lenses, if that's what you want to use them with. (The 28-135 and 50/1.8 are EF lenses... the 12-24 is too, tho won't very likely be used for close-ups... the 15-85, your 18-55, the 55-250 are all EF-S lenses). There are cheaper macro extension tube sets... but the ones around $50-60 US are pretty flimsy and the ones for $25 or less do not have the electronic contacts for auto focus or aperture control... so are a pain in the arse to use. I don't recommend the sub-$25 US, particularly (they are okay with adapted, vintage lenses... just not so much with modern electronically controlled lenses).
Have fun shopping!
Sounds like a great trip!