Variant of larsmans's proposed method:
Save your untrackfiles list:
git ls-files --others --exclude-standard > /tmp/my_untracked_files
Save your git configuration:
mv .git/config /tmp/
Then perform larsmans's first steps:
rm -rf .git
git init
git add .
Restore your config:
mv /tmp/config .git/
Untrack you untracked files:
cat /tmp/my_untracked_files | xargs -0 git rm --cached
Then commit:
git commit -m "Initial commit"
And finally push to your repository:
git push -u --force origin master