A good auto locksmith can program a new key for your car, although it won't be cheap. He would look up your make, model, year, and trim, then bring the right blank key accordingly. Then he would follow a process for the specific car where he first cuts the key to fit, then connects his key programmer to the car's computer, then follows some kind of sequence to download the car's code to the key.
My experience on a Toyota is that most places will charge around $150-$300 (and up). If you can get the car to a dealership, it may be your best bet, and you will get an "official" OEM key instead of some weird-looking off-brand key. You may want to see which is cheaper - towing the car to the dealer and paying them to explore
, or paying a locksmith to come to your car. You may find that the dealer is cheaper, and foolproof.