Both seem to be valid and accpeted options.

A google search as follows:

Velikiy +Novgorod site:.gov

which searches for .gov websites gets 10x more responses than Veliky or Velikii. So that gives you a style standard from the U.S. government.

HERE ARE A FEW SAMPLES OF US GOVT WEBSITES:

A Russian girl meets her newborn brother as part of Velikiy Novgorod hospital’s family centered maternity care program. (Photo: USAID / John Snow Inc.)
http://geneva.usmission.gov/2010/06/14/us-russian-mch/

In 1992 UNESCO added its chief monuments to the World Heritage list. In 1998, the city was officially renamed Velikiy Novgorod, recalling its medieval title "Lord Novgorod the Great".
http://www.cityofrochester.gov/article.aspx?id=8589938076

Residents of Velikiy Novgorod should apply through the Pony Express office at Gzen River Embankment 11, office 410, or by calling (8162) 335167.
http://stpetersburg.usconsulate.gov/how-to-apply.html

Creator/Author Popov, Alexey V. [Novgorod State University, B.S.-Peterburgskaya Street 41, 173003 Velikiy Novgorod (Russian Federation)]
http://www.osti.gov/energycitations/product.biblio.jsp?osti_...

I recommend you the first variant (Veliky).
Velikiy is correct from the relevant transliteration rule point of view and closer to Russian pronounciation.
But you could hardly find similar ending (-iy) in any serious book with a list of geographic names (like English - Russian Dictionary or translated guides) published in Russia.
I should add that my name is Dmitry. I never put it like Dmitriy.
My mother originated from Nizhny Novgorod region. You could refer to official site of this city administration. http://admgor.nnov.ru/english/index.html