The answer to your question is yes. A permutation matrix is in fact a product of permutation matrices associated to transpositions, which means a matrix obtained from the identity matrix by interchanging two rows. Reduce the problem to this case and notice that this case can be easily deduced from the case of the $2\times 2$ matrix $$\left(\begin{array}10 & 1 \\ 1 & 0\end{array}\right).$$
This matrix can be transformed into the identity matrix by using the following elementary transformations (which correspond to triangular matrices): add the second row to the first, substract the first column from the second, substract the first row from the second, and last multiply the second row by $-1$.
Moreover, in the paper of Nagarajan et al., Products of three triangular matrices, Linear Algebra and its Applications, 292(1999), 61-71 it is proved that any matrix $n\times n$ over a field is a product of at most three triangular matrices.
There are so few matrices satisfying the conditions that writing them out explicitly is probably the fastest and most reliable way of solving this. Elegant solutions are great, but if there is any kind of time pressure, it is usually best to go with the first correct solution!
$A_1=\begin{pmatrix}1&1&1\\1&0&0\\1&0&0\end{pmatrix},$
$A_2=\begin{pmatrix}0&1&1\\1&1&0\\1&0&0\end{pmatrix},$
$A_3=\begin{pmatrix}0&1&1\\1&0&0\\1&0&1\end{pmatrix},$
$A_4=\begin{pmatrix}1&0&1\\0&0&1\\1&1&0\end{pmatrix},$
$A_5=\begin{pmatrix}0&0&1\\0&1&1\\1&1&0\end{pmatrix},$
$A_6=\begin{pmatrix}0&0&1\\0&0&1\\1&1&1\end{pmatrix},$
$A_7=\begin{pmatrix}1&1&0\\1&0&1\\0&1&0\end{pmatrix},$
$A_8=\begin{pmatrix}0&1&0\\1&1&1\\0&1&0\end{pmatrix},$
$A_9=\begin{pmatrix}0&1&0\\1&0&1\\0&1&1\end{pmatrix},$
$A_{10}=\begin{pmatrix}1&1&0\\1&1&0\\0&0&1\end{pmatrix},$
$A_{11}=\begin{pmatrix}1&0&1\\0&1&0\\1&0&1\end{pmatrix},$
$A_{12}=\begin{pmatrix}1&0&0\\0&1&1\\0&1&1\end{pmatrix},$
$A_1,A_{12}$ have many solutions; $A_6,A_8,A_{10},A_{11}$ have no solutions; $A_2,A_3,A_4,A_5,A_7,A_9$ each have a unique solution.
It is easy to see whether the zero-determinant cases have 0 or many solutions because they have a repeated row. Where the rows 2 and 3 are the same there are many solutions (because we want a value 0 in each case for that component of the vector). Where one of the repeat rows is 1 we have zero solutions.
Best Answer
As you say, there are $n$ elements along the diagonal. Each of them can be anything. That leaves $n^2-n$ elements, which occur in pairs symmetric across the diagonal. The entries of each pair must agree, but different pairs can have different values. There are $\frac 12(n^2-n)$ pairs. That gives $n+\frac 12(n^2-n)=\frac 12n(n+1)$ free elements in an $n \times n$ symmetric matrix.