Google Spreadsheet自体を作成する方法について以下記載します。

OAuthの設定、および、スプレッドシートへのアクセスについては以下の記事が参考になりました。
PythonからOAuth2.0を利用してスプレッドシートにアクセスする

また、Google Spreadsheetの作成自体については以下が参考になりました。
docs_v3_example.py
Create new spreadsheet (Google API / Python)

Python 2.7.10, gdata 2.0.18の環境で動作を確認しています。

# !/usr/bin/env python
# -*- coding: utf-8 -*-

from oauth2client.service_account import ServiceAccountCredentials
import gdata.docs.client

# name definitions
APP_NAME = 'GDataDocumentsAPISample'
name_spr = 'Sample Spreadsheet'

# resources for credential
json_key = 'gspread-test.json'
scope = ['https://docs.google.com/feeds']

# create goole data docs client
client = gdata.docs.client.DocsClient(source=APP_NAME)
client.http_client.debug = True
# client.http_client.debug = False

# create credentials
credentials = ServiceAccountCredentials.from_json_keyfile_name(json_key, scope)
auth_token = gdata.gauth.OAuth2TokenFromCredentials(credentials)

# authorise
auth_token.authorize(client)

# create document as spreadsheet
document = gdata.docs.data.Resource(type='spreadsheet', title=name_spr)
document = client.CreateResource(document)

# add ACL to  spreadsheet
acl_entry = gdata.docs.data.AclEntry(
    scope=gdata.acl.data.AclScope(value='hoge@foo.bar', type='user'),
    role=gdata.acl.data.AclRole(value='writer'),
)
client.AddAclEntry(document, acl_entry, send_notifications=False)
			    
print('Created:', document.title.text, document.resource_id.text)

少しハマったところとして…　Oauthを実行する場合のアカウントは自分のGoogleアカウントとは異なり、name@projectname.iam.gserviceaccount.com がownerとなり、デフォルトでprivateなのでacl_entryを設定してやらないとGoogle Drive上でSpreadsheetが表示できません。