I'm sort of wondering too why trees won't work. A regular tree can have problems given worst-case input, but a 2-3-4 tree fits all of the requirements reasonably well. Depending on your needs, you may also want to look into a regular binary tree with insert at root, which while it does not defend against worst-case input, does keep the most recently added items closest to the root, where they can be accessed most quickly.

Or you could just use a regular binary tree, but rebalance it every x number of items. Assuming you do the rebalancing efficiently (and I'm doing my calculations correctly), rebalancing should be a O(n) process, meaning you can run it every so often without too big a loss in efficiency.

Bottom line, you're making a mountain out of a molehill if it's only 1000 items. You can use arrays and nobody will be able to tell the difference in your prototype. Later on, I'm sure there are 2-3-4 or red/black tree classes for C that you can use with minimal trouble, or you can borrow any algorithms book and write your own class in a few hours.