EDIT: This is true up to dimension 8. An article that I have, Hsia, J.S. Two theorems on integral matrices. Linear Multilinear Algebra 5, 257-264 (1978). I put a pdf at TERNARY with the name Hsia_1978.pdf. He calls the the Completion problem, answers it in Theorem 2. He also gives my dimension 9 example, page 262. So, I was only about 34 years late. This reference was provided on MO by someone anonymous using the name http://en.wikipedia.org/wiki/Yazdegerd_III , which I really thought was a Dr. Seuss name because of the rhyme, compare http://en.wikipedia.org/wiki/Yertle_the_Turtle_and_Other_Stories and see http://en.wikipedia.org/wiki/Dr._Seuss_bibliography#Dr._Seuss_books
ORIGINAL: Finally got it. The task is impossible for a 9 by 9 matrix with first row $ (1,1,1,1,1,1,1,1,1 ). $
I Win.
The trick is that $ x^2 \equiv x \pmod 2. $ So, if I take any ODD number $k,$ and consider a $k^2$ by $k^2$ matrix, then take the first row of the matrix to be all 1's, we find that there are NO other rows of the same length orthogonal to the first row, because a row $(x_1, \ldots, x_{k^2})$ is required to have squared length $k^2$ in this problem, so $ \sum_{j=1}^{k^2} \; x_j^2 \; = \; k^2 \equiv 1 \pmod 2. $ Then the dot product with the row of all 1's is $ \sum_{j=1}^{k^2} \; x_j \; \equiv \; \sum_{j=1}^{k^2} \; x_j^2 \equiv 1 \pmod 2. $ That is, the dot product is odd and therefore nonzero. So, in fact, there are just no orthogonal rows of the same squared length, you cannot fill in the entire matrix, you cannot even get a second row.
EDIT: a similar thing can be done for any $n$ by $n$ matrix when $ n \equiv 1 \pmod 8. $ So, for example, when $n = 17,$ the matrix cannot be filled in as desired when the first row is $ (3,1,1,1,1, 1,1,1,1, 1,1,1,1, 1,1,1,1). $ The entries do not need to be 1, just odd. So, there should be infinitely many first rows (for each $n$) for which this task is impossible, as long as we have $ n \equiv 1 \pmod 8. $ Yes, that is quite easy. Gauss showed that every number is the sum of three triangular numbers, such being $(1/2)(p^2 +p)$ for integer $p \geq 0.$ Now, $8 \cdot (1/2)(p^2 +p)= 4 p^2 + 4 p.$ So we can represent any multiple of 8 as $4 p^2 + 4 p + 4 q^2 + 4 q + 4 r^2 + 4 r$ with integers $p,q,r \geq 0.$ As a result, we may have any odd square we like (no smaller than $n$) as the sum of the squares of $ (2p+1,2q+1,2r+1,1,1,1, \ldots, 1,1,1,1) $ with the row being of length $ n \equiv 1 \pmod 8. $ As a result, we can have the length be any odd integer we like, as long as it is at least $\lceil \; \sqrt n \; \rceil.$
EDDDITTT: the part about Gauss and triangular numbers says something stronger, making for far more counterexamples: with $ n \equiv 1 \pmod 8, $ we may specify any $n-3$ odd numbers we like, then use the final three positions (also odd numbers) to force integral length, as requested in the original problem. Hence this example: $ (1,3,5,7,9,11,13,17,25) $ which has length 37. But any other integer vector of length 37 has an odd, hence nonzero, inner product with this vector.