.travis.yml ended up looking like this:

language: go

go: 1.3.1

install:
  - export PATH=$PATH:$HOME/gopath/bin
  - go get github.com/tools/godep
  - godep restore

script:
  - go test
  - test -z \"$(go fmt ./...)\"

edit: Pull Request to travis-build here.<br> edit 2: Pull Request Accepted! TravisCI will now install Godeps without editing a .travis.yml