I am tempted to see if char* str[]; is a valid syntax or not

I think it's valid, but it does make things tricky ... and maybe it's that trickiness that inspired this thread in the first place.
It gets a lot easier if we're allowed to declare the struct as:

struct _Edje_Message_String_Set
{
   int count;
   AV * str;
};
[download]

Here's a demo using that very struct declaration.

# struct.pl #
use strict;
use warnings;

use Inline C => Config =>
  BUILD_NOISY => 1,
  CLEAN_AFTER_BUILD => 0,
  USING => 'ParseRegExp',
;

use Inline C => <<'EOC';

struct _Edje_Message_String_Set
{
   int count;
   AV * str;
};

typedef struct _Edje_Message_String_Set EdjeMessageStringSet;

void struct_size(void) {
  printf("Size of _Edje_Message_String_Set struct: %d\n",
         sizeof(EdjeMessageStringSet) );
}

EdjeMessageStringSet * _new(AV * val_arr) {
  EdjeMessageStringSet *message;
  /* int i; */
  /* SV ** elem; */

  Newx(message, 1, EdjeMessageStringSet);
  if(message == NULL)
    croak("Failed to allocate memory in _new function");

  message->count = av_len(val_arr) + 1;
  message->str   = val_arr;

  return message;
}

void _iterate(EdjeMessageStringSet * strs) {
  int i;
  SV ** elem;

  for(i = 0; i < strs->count; i++) {
    elem = av_fetch(strs->str, i, 0);
    printf("%s\n", SvPV_nolen(*elem));  
  }
}

void DESTROY(EdjeMessageStringSet * x) {
  Safefree(x);
  printf("destroyed _new EdjeMessageStringSet*\n");
}

void foo(AV * arref) {
  EdjeMessageStringSet *m;
  m = _new(arref);
  _iterate(m);
  DESTROY(m);
}

EOC

struct_size();
my @in = ("hello foo", "hello bar","hello world", "goodbye");

# The XSub foo() will create a new EdjeMessageStringSet object
# using _new(), then pass that object to _iterate() which
# prints out all of the strings contained in the object.
# Finally, foo() calls DESTROY() which frees the memory that
# was assigned to create the EdjeMessageStringSet object.
foo(\@in);
[download]

For me, that outputs:

Size of _Edje_Message_String_Set struct: 16
hello foo
hello bar
hello world
goodbye
destroyed _new EdjeMessageStringSet*
[download]

Cheers,
Rob