1- I don't know if there is a way to see if the database is new through Titan. You could check to see if the directory where BerkeleyDB will be stored exists before you start Titan.
2/3- Probably your best bet would be a hardcoded vertex with an indexed property "version". Do a look up within the (nearly empty) index on "version" at the start and base your logic on those results.
An aside, you might be interested in Titanium[0]. We're gearing up for a big release in the next week or so that should make it much more useful[1].
[0] http://titanium.clojurewerkz.org/
[1] http://blog.clojurewerkz.org/blog/2013/04/17/whats-going-on-with-titanium/