How to index JSON data in PostgreSQL 9.3, when its key is unknown?

You haven't clearly defined what you want; here's what I'm assuming you mean:

Create an index that lets me test whether any given json value (example above) contains a key named 'k'

I think this is only possible (sanely) in 9.3 if the json structure is uniform, i.e. you always have an array of flat objects. If that's the case you can extract an array of keys, e.g.

regress=> create table x as select '[
  {"1111" : "aaaa"},
  {"2222" : "bbbb"},
  {"3333" : "cccc"}
]'::json as col;
SELECT 1

regress=> select array_agg(k) from x, lateral json_array_elements(col) e, lateral json_object_keys(e) k;
    array_agg     
------------------
 {1111,2222,3333}
(1 row)

and wrap that up in an SQL function:

CREATE OR REPLACE FUNCTION json_array_object_keys(json) RETURNS text[] AS $$
select array_agg(k) FROM lateral json_array_elements($1) e, lateral json_object_keys(e) k;
$$ LANGUAGE sql IMMUTABLE;

which works as follows:

craig=> SELECT json_array_object_keys(col) from x;
 json_array_object_keys 
------------------------
 {1111,2222,3333}
(1 row)

Then create a GIN array index on the expression:

CREATE INDEX json_nested_keys_idx ON x USING GIN( json_array_object_keys(col) );

(warning, such an index will be very slow to update, it will slow down insert/update/delete a lot)

and use it as follows:

SELECT * FROM x WHERE json_array_object_keys(col) @> ARRAY['1111'];

You can't do indexed searches for LIKE with the array approach; you'd have to squish the array into a text literal:

CREATE OR REPLACE FUNCTION json_array_object_keys_delim(json) RETURNS text AS $$
select array_to_string(array_agg(k),'|') FROM lateral json_array_elements($1) e, lateral json_object_keys(e) k;
$$ LANGUAGE sql IMMUTABLE;

CREATE INDEX json_tgrm_keys_idx ON x USING GiST( (json_array_object_keys_delim(col)) gist_trgm_ops);

SELECT * FROM x WHERE json_array_object_keys_delim(col) LIKE '%111%';