Is there a way to create an auto increment primary key column when creating a new Shapefile in QGIS?
As far as I know, Shapefiles have no concept of primary key or auto increment data types.
What you can do is use Field Calculator to populate a column with row number.
I get this question a lot on the pyshp mailing list and underdark is correct. The shapefile format provides no unique identifiers for geometry or attribute records.
The object id, feature id, or other GUID is a trapping of the software you use and is just a row number assigned as the records are read in. The only options are to assign a new attribute using scripting or spreadsheet software, or load the data into a spatial database.
A Shapefile has a OBJECTID field; which serves as its key and primary index which should suit your purposes.