You would have to buy a new keyfob (do so before you loose your remaining one! If no fobs left, that's the pricy ECU replacement...), and have a dealer reprogram it for you. (The 2004s require a tech tool for the reprogramming, the classic Prius you could do yourself with a specific "dance")
Pricing on the keyfob and on the programming (labor) costs vary by dealer.
From the 2004 Prius parts database on the Prius-2G yahoogroup:
<quote>
Part Number \/ Description Price Location Contact Notes (dependencies,
conflicts, other) Edit Delete
89071-47180 2004 keyfob WITHOUT Smart Start & Entry $144.17
Conicelli Toyota - PA Tom Rielli - 800-825-7128 ext.2653 Mention you
are a Prius Club Member for this discounted price. List $192.33 Edit
Delete
89904-47061 2004 keyfob WITH Smart Start & Entry $160.50 Conicelli
Toyota - PA Tom Rielli - 800-825-7128 ext.2653 Mention you are a
Prius Club Member for this discounted price. List $214.00 Edit Delete
</quote>
I would recommend that you have the dealer delete all keys (except the one that is used to start the key delete process), and then add any new keys that you have. That way, you don't have to worry about someone finding your old keyfob and using it to steal your car.
BTW: for classic Prius, I suggest:
http://www.coastaletech.com/carkeys.htm look through the programming info for an idea of what your dealer can do for your 2004 (although the programming instructions only work on a 2001-2003 Prius)