Definition of $\frac{dy}{dx}$ where we cannot write $y=f(x)$ Informally, I can say that "for a small unit change in $x$, $\frac{dy}{dx}$ is the corresponding small change in $y$". This is however a bit vague and imprecise, which is why we have a formal definition, such as: 
Where $y=f(x)$, we define $$\frac{dy}{dx}=\lim_{h\rightarrow 0} \frac{f(x+h)-f(x)}{h}. $$
$$$$
But what about if we are unable to express $y$ as a function of $x$? (To pick a random example, say we have $\sin (x+y) + e^y = 0$.)
Then what would the general definition of $\frac{dy}{dx}$ be? (How would the above definition be modified?)
$$$$
To elaborate, applying the $\frac{d}{dx}$ operator to my random example, we get $$\left(1+\frac{dy}{dx}\right)\cos(x+y)+e^{y}\frac{dy}{dx}=0 \implies \frac{dy}{dx}=\frac{-\cos(x+y)}{\cos(x+y)+e^{y}}.$$
Again, I can say that "for a small unit change in $x$, $\frac{dy}{dx}$ is the corresponding small change in $y$". But what would the corresponding precise, formal definition be?

Apparently you are mixing two things: "definition of derivative" and "a practical method of calculate derivative in a certain context". The limit definition is not supposed to be used for calculating derivatives of complicated functions, rather it is supposed to be used to prove theorems and these theorems turn out to be the basis of techniques of differentiating complicated functions.
Thus when you are applying operator $d/dx$ on $$\sin(x + y) + e^{y} = 0\tag{1}$$ you are in effect assuming that the equation $(1)$ defined a genuine function $y = f(x)$ of $x$ in a certain interval and then you are using the basic rules of differentiation (mainly sum rule and chain rule).
Note that in general not every equation of type $f(x, y) = 0$ leads to a function $y = g(x)$. In case of equation $(1)$ there is a genuine function $y = f(x)$ and hence on the basis of this assumption we can differentiate the equation $(1)$ and find $f'(x)$ with some algebraic manipulation.
It many cases it is not possible/desirable to use the limit definition of derivative to calculate it. The example you gave is one such case because here we don't have an explicit formula for $f(x)$ in terms of elementary functions. Note that the definition of $f'(x)$ does not assume that there should be an explicit formula to calculate $f(x)$ in terms of elementary functions and hence we can very well talk about $f'(x)$ where $f(x) = y$ is given by the equation $(1)$ in implicit manner.
