For example, $(\exists x) \,\,\forall y \in Y \,\, P(x,y)$. Here $\exists x$ does not have universe of discourse . In this case, can normal rule for negating the sentence/statement still be used?
Using the rule usually used, negation of the above would be $(\forall x) \exists y \in Y (\neg P(x,y))$, but I am not sure if that's valid.
Yes, it is valid to negate the statement just as you did.
The negated statement faces the same problem as the original (in that there's lack of a universe of discourse for the quantified $x$), but the negation of the original statement proceeds just as you'd expect it to, and your negation of the original is correct.