I have figured it out.
The way I included degeneracy was correct but I made some subtle mistakes during substitution of some parameters.
The formula for $\ln(\Omega)$ when degeneracy $g_j$ is taken into account is:
$$\ln(\Omega)= N \cdot \ln(N) - N - \sum^n_{j=1}[n_j \cdot \ln(n_j) - n_j] + \sum^n_{j=1} [\ln(g_j) \cdot n_j]$$
Substituting $n_j = g_j \cdot \frac{N}{Z} \cdot e^{\beta E_j}$ (I erroneously left out the $g_j$ during this substitution) along with rewriting, splitting the summations and simplifying eventually gives me:
$$\ln(\Omega) = N \cdot \ln(Z) - \beta U$$
Which is the exact equation as when degeneracy is not taken into account, and thus I get the same value for $\beta$ when taking the derivative of $S = k_B \cdot \ln(\Omega)$ and putting it next to the equation of entropy $dS = \frac{dU}{T}$.
Details Derivation
Formula for $\ln(\Omega)$ when taking degeneracy into account
$$\ln(\Omega)= N \cdot \ln(N) - N - \sum^n_{j=1}[n_j \cdot \ln(n_j) - n_j] + \sum^n_{j=1} [\ln(g_j) \cdot n_j]$$
According to Boltzmann Statistics $n_j = g_j \frac{N}{Z} e^{\beta E_j}$. Furthermore, $\ln(n_j) = \ln\big(g_j \frac{N}{Z}\big) + \beta E_j$. Substituting these parameters:
$$\ln(\Omega)= N \cdot \ln(N) - N - \sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j}\cdot \bigg(\ln\big(g_j \frac{N}{Z}\big) + \beta E_j\bigg) - g_j \frac{N}{Z} e^{\beta E_j}\bigg] + \sum^n_{j=1} \bigg[\ln(g_j) \cdot g_j \frac{N}{Z} e^{\beta E_j}\bigg]$$
Splitting the 1st summation into 3 summations between the + and – signs and removing the brackets that appear after splitting:
$$\ln(\Omega)= N \cdot \ln(N) - N - \sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j}\cdot \ln\big(g_j \frac{N}{Z}\big)\bigg] - \beta\sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j} \cdot E_j)\bigg] + \sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j}\bigg] + \sum^n_{j=1} \bigg[\ln(g_j) \cdot g_j \frac{N}{Z} e^{\beta E_j}\bigg]$$
The 2nd summation is equal to the total energy $U$, and the 3rd summation is equal to the total number of particles $N$ which cancels the $-N$ term.
$$\ln(\Omega)= N \cdot \ln(N) - \sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j}\cdot \ln\big(g_j \frac{N}{Z}\big)\bigg] - \beta U + \sum^n_{j=1} \bigg[\ln(g_j) \cdot g_j \frac{N}{Z} e^{\beta E_j}\bigg]$$
In the 1st summation term, substituting $\ln\bigg(g_j \frac{N}{Z}\bigg) = \ln(g_j) + \ln\big(\frac{N}{Z}\big)$ and then splitting that summation between the newly created + sign as well and removing the appearing brackets:
$$\ln(\Omega)= N \cdot \ln(N) - \sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j}\cdot \ln(g_j)\bigg] - \ln\big(\frac{N}{Z}\big) \sum^n_{j=1}\bigg[g_j \frac{N}{Z} e^{\beta E_j}\bigg] -\beta U + \sum^n_{j=1} \bigg[\ln(g_j) \cdot g_j \frac{N}{Z} e^{\beta E_j}\bigg]$$
The first and 3rd summations cancel each other out. The 2nd summation is equal to $N$, giving:
$$\ln(\Omega)= N \bigg(\ln(N) - \ln\big(\frac{N}{Z}\big)\bigg) - \beta U$$
Since, $\ln(N) - \ln\big(\frac{N}{Z}\big) = \ln(Z)$, this gives:
$$\ln(\Omega) = N\cdot \ln(Z) - \beta U$$
The $Z$ and $U$ are functions of $\beta$. Equation for entropy is $S = k_B \cdot \ln(\Omega)$. Thus deriving $\frac{dS}{d\beta}$:
$$\frac{dS}{d\beta} = k_B \bigg(\frac{N}{Z} \cdot \frac{dZ}{d\beta} - \bigg(U + \beta \frac{dU}{d\beta}\bigg)\bigg)$$
Since $\frac{dZ}{d\beta} = \frac{UZ}{N}$ this gives:
$$\frac{dS}{d\beta} = -k_B \cdot \beta \frac{dU}{d\beta}$$
Knowing that $dS = \frac{dU}{T}$ (when a fixed volume is assumed), this yields:
$$\beta = - \frac{1}{k_B T}$$