I am now looking into an option of explicitly compiling header perl.h directly into my extension library. But I am getting the error below.

My Error:

x86_64-linux-gnu-gcc -pthread -DNDEBUG -g -fwrapv -O2 -Wall -Wstrict-prototypes -g -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -fPIC -I/usr/lib/perl/5.18/CORE -I/usr/include -I/usr/local/include -I/usr/include/python3.4m -I/home/losintikfos/git/testproj/env/include/python3.4m -c src/pymechanize.c -o build/temp.linux-x86_64-3.4/src/pymechanize.o -O0 -g3 -Wall -c -fmessage-length=0 -Wl,-E -fstack-protector -L/usr/local/lib -L/usr/lib/perl/5.18/CORE -lperl -ldl -lm -lpthread -lc -lcrypt -D_REENTRANT -D_GNU_SOURCE -DDEBIAN -fno-strict-aliasing -pipe -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -I/usr/lib/perl/5.18/CORE
In file included from /usr/lib/perl/5.18/CORE/perl.h:2513:0,
                 from src/pymechanize.c:297:
/usr/lib/perl/5.18/CORE/handy.h:873:1: error: unknown type name ‘EXTCONST’
 EXTCONST U32 PL_charclass[];
 ^
/usr/lib/perl/5.18/CORE/handy.h:873:14: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘PL_charclass’
 EXTCONST U32 PL_charclass[];
              ^
In file included from /usr/lib/perl/5.18/CORE/regexp.h:21:0,
                 from /usr/lib/perl/5.18/CORE/perl.h:3472,
                 from src/pymechanize.c:297:
/usr/lib/perl/5.18/CORE/utf8.h:100:10: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘unsigned’
 EXTCONST unsigned char PL_utf8skip[];
          ^
In file included from src/pymechanize.c:297:0:
/usr/lib/perl/5.18/CORE/perl.h:4254:10: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘char’
 EXTCONST char PL_warn_uninit[]
          ^
/usr/lib/perl/5.18/CORE/perl.h:4256:10: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘char’
 EXTCONST char PL_warn_uninit_sv[]
          ^
/usr/lib/perl/5.18/CORE/perl.h:4258:10: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘char’
 EXTCONST char PL_warn_nosemi[]
          ^
/usr/lib/perl/5.18/CORE/perl.h:4260:10: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘char’
 EXTCONST char PL_warn_reserved[]
          ^
/usr/lib/perl/5.18/CORE/perl.h:4262:10: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘char

....

Compiled EXTERN.h before perl.h removed the errors:

/usr/lib/perl/5.18/CORE/handy.h:873:1: error: unknown type name ‘EXTCONST’
 EXTCONST U32 PL_charclass[];
 ^
..

But doesn't resolve the issue undefined symbol: PL_utf8skip.

But doesn't resolve the issue undefined symbol: PL_utf8skip

As already intimated, the symbol should be resolved by linking to libperl.a - and you seem to be linking to that file.
So ... you need to find out why that's not doing the trick.

Could it be to do with the order in which you're linking to the various libraries ? I don't know.
We do know that libperl.a (probably /usr/lib/perl/5.18/CORE/libperl.a) is being found - otherwise it's a fatal error at build time.

Cheers,
Rob