My opinion:

The company should be paying for the party. Either at a restaurant or at work.

If they are really that cheap, then invite co-workers to gather at a restaurant for a send off, dutch treat. As for a gift, a plaque or small trophy wouldn't be too expensive and could be financed through donations.