Again I end up answering my won question.
Ill put up the code which wrks
pj_caching_pool cp;
pj_pool_t *pool;
pj_status_t status = PJ_SUCCESS;
pj_str_t pj_uri;
pjsua_msg_data msg_data;
pjsua_msg_data_init(&msg_data);
pj_uri = pj_str((char *)uri);
pj_caching_pool_init(&cp, &pj_pool_factory_default_policy, 0);
pool= pj_pool_create(&cp.factory, "header", 1000, 1000, NULL);
for(NSString *key in [headers allKeys]){
NSLog(@"Call.m key value in call %@,%@",key,[headers objectForKey:key] );
pj_str_t hname = pj_str((char *)[key UTF8String]);
char * headerValue=(char *)[(NSString *)[headers objectForKey:key] UTF8String];
pj_str_t hvalue = pj_str(headerValue);
pjsip_generic_string_hdr* add_hdr = pjsip_generic_string_hdr_create(pool, &hname, &hvalue);
pj_list_push_back(&msg_data.hdr_list, add_hdr);
}
status = pjsua_call_make_call(acc_id, &pj_uri, 0, NULL, &msg_data, call_id);
pj_pool_release(pool);