[Маэстро]

Array.prototype.splice.call(myObj, 2, 1);

Вообще мне нравятся решения "в одну строку". Я, пожалуй, всё же возьму Ваш вариант. Только у меня пока еще есть смутные сомнения насчет него - надо всячески потестировать при разных вариантах заполнения объекта и удаления его свойств, проверить быстродействие.

Если и это не подходит, значит, придётся реализовывать своюь структуру данных, где выборка по ключу будет O(1), и в которой так же можно будет менять ключ.
мне кажется, что это будет трудно

А вот посмотрите/прокомментируйте, пожалуйста, примерчик, который я нашел в инете. В частности касательно установки length:

//for (i in obj) length++; obj.length = length; // melky

Array.prototype.associate = function(keys){
    var obj = {}, length = Math.min(this.length, keys.length);
    for (var i = 0; i < length; i++) obj[keys[i]] = this[i];
    return obj;
};

var hash = ['one', 'three', 'two'].associate(['first','3','2']);

var string = '';

for (var i in hash) string += i + ':' + hash[i] + '; ';

alert(string);
// Chrome: 2:two; 3:three; first:one;
// Opera:  2:two; 3:three; first:one;
// FF: first:one; 3:three; 2:two; 
// IE: first:one; 3:three; 2:two;