Where does entropy-increasing waste heat go during non-reversible processes? The first law of thermodynamics states that energy is conserved. $\Delta U = Q - W$ (internal energy change is the difference between external energy supplied and work done on the environment).
The second law of thermodynamics states that entropy is never decreasing and is only constant in reversible thermodynamic processes. In a non-reversible thermodynamic process, the entropy of the universe is increased.
Suppose we have an abstract 1-dimensional cellular automata universe consisting of 0s (empty space) and 1s (energy/atoms) but obeying the first and second laws of thermodynamics. The 1s are drawn together via "gravity" forces:
t0: 0010000100
t1: 0001001000
t2: 0000110000

Unlike microscopic time-reversible phenomena, let us assume that the collision of the two 1s generates entropy.
Q1: Would the final state of this universe be cycling through all possible $10 \choose 2$ states, as that is the maximum entropy configuration?
Q2: If the answer to Q1 is yes, then that implies a set of dynamics that encourage an equilibrium distribution of two 1s over the 10 position. If we have any less or more than 2 1s, wouldn't that violate conservation of energy? (the total energy of the starting system is 2).
Q3: Where does entropy "go" when it is produced? In this toy universe I have no way to embody any other non-zero energy than "1". If we choose to introduce a new letter "H" as an "entropy" particle, does this violate the first law of thermodynamics? (since the new energy of the system is 1 + 1 + H). Does entropy occupy space?
t1: 0001001000
t2: 000011H000

Or is it a "hidden state" a cell that follows energy around?
The bigger question here is that when I think of living things perform some thermodynamically irreversible work to lower their entropy, I am wondering where that entropy "goes".  If entropy is created but mass and energy are conserved, how do we end up with heat "for free" without changing total energy?
t1: 0001001000
h1: 0000000000

t2: 0000110000
h2: 00000H0000

Q4: Are random dynamics required here in order to eventually reach a state of maximum entropy? One way to model this would be to treat H as "non-useful work" that fills up the universe and potentially creates more H when it interacts with non-H cells.
Q5: Are there any limitations to this 1D universe in my understanding of how the first and second law of thermodynamics works?
 A: Entropy and life
Entropy is an observer's uncertainty about the state of a system. A measurement (macro state) gives you a belief distribution over possible configurations (micro states) the system could be in. The Shannon entropy of this belief measures the observer's uncertainty. A uniform distribution over consistent states simplifies the entropy to the log of the number of consistent states.
Entropy increases if the observer makes stochastic predictions of how the state evolves. For example, thermodynamics uses Langevin dynamics that have Brownian motion. The dynamics of the belief distribution are known as the Fokker-Planck equation. The entropy increases faster the faster the micro states move, that is, the higher the temperature of the system.
Systems that exist for some time need to remain within a distribution that lets us identify them. For example, there is a distribution of all particle arrangements that we call "dog" that any dog will remain it throughout its lifetime. Such systems appear as if they used work to bring their state toward higher probability under their class to resist the entropy increase caused by the Brownian motion. As a result of bounding their entropy, they increase the entropy of their surroundings.
Individual answers
Q1: Would the final state of this universe be cycling through all possible 10 over 2 states, as that is the maximum entropy configuration?
You didn't clearly define the dynamics of the system, you just said that there is a gravitational force and the system obeys the laws of thermodynamics.
If you describe the system as deterministic and have full knowledge about the initial condition, your belief over its state is a point mass distribution and remains one as time passes, so the entropy is always zero and the dynamics are reversible.
If there is stochasticity in addition to an attracting force between particles (for example particles are repelled in random directions on collision), then the system will converge to a stationary distribution where they wiggle around near each other, which is not a uniform distribution over all possible system states.
Q2: If the answer to Q1 is yes, then that implies a set of dynamics that encourage an equilibrium distribution of two 1s over the 10 position. If we have any less or more than 2 1s, wouldn't that violate conservation of energy? (the total energy of the starting system is 2).
One way to define the total energy that it is a quantity that is preserved in a system. Defining the total energy is a way to express symmetries in a system that the system will obey. This defines a constraint on the dynamics. The first law of thermodynamics is thus more of a definition than a law.
For your system, you defined the total energy to be the sum of "1" particles. This means the number of "1" particles cannot change from what it is during the initial condition. This tells us that your system can only reach the 10 over 2 different states that contain exactly 2 "1" particles rather than the 2^10 states.
Q3: Where does entropy "go" when it is produced? In this toy universe I have no way to embody any other non-zero energy than "1". If we choose to introduce a new letter "H" as an "entropy" particle, does this violate the first law of thermodynamics? (since the new energy of the system is 1 + 1 + H). Does entropy occupy space? Or is it a "hidden state" a cell that follows energy around?
Entropy is not a particle and it is also not conserved over time. One way to related entropy and energy is via the Gibbs free energy that subtracts energy minus entropy. It measures the amount of energy that we can direct into work, i.e. the amount of energy that is not lost to entropy.
The bigger question here is that when I think of living things perform some thermodynamically irreversible work to lower their entropy, I am wondering where that entropy "goes". If entropy is created but mass and energy are conserved, how do we end up with heat "for free" without changing total energy?
Systems that persist over some duration of time, including living things, have to persist stochasticity in the state dynamics to remain with some distribution of states in which we still identify them as the thing they are. For example, if the particle configuration of a dog would change out of the distribution of particle configurations that we consider to be dogs, we would not call it a dog anymore.
I think your question may be what is known as Schrödinger's "paradox":

Since life approaches and maintains a highly ordered state, some argue that this seems to violate the aforementioned second law, implying that there is a paradox. However, since the biosphere is not an isolated system, there is no paradox. The increase of order inside an organism is more than paid for by an increase in disorder outside this organism by the loss of heat into the environment. By this mechanism, the second law is obeyed, and life maintains a highly ordered state, which it sustains by causing a net increase in disorder in the Universe. In order to increase the complexity on Earth—as life does—free energy is needed and in this case is provided by the Sun.

Q4: Are random dynamics required here in order to eventually reach a state of maximum entropy? One way to model this would be to treat H as "non-useful work" that fills up the universe and potentially creates more H when it interacts with non-H cells.
The maximum entropy state depends on the system. If the system is modeled as deterministic and the initial condition is fully known, then the maximum entropy is zero and would be reached from the beginning.
If the dynamics are stochastic, the state belief will over time converge to the least certain distribution. At this point, entropy does not increase anymore. This is the distribution that you think the system state is in if you don't know an initial condition. For this to happen, the dynamics need to be weakly mixing.
Q5: Are there any limitations to this 1D universe in my understanding of how the first and second law of thermodynamics works?
Yes, if the dynamics of your system are modeled as deterministic and you have full knowledge of the initial condition, then you can deterministically predict its state into the future and the belief entropy remains zero. You need uncertainty in either the dynamics or the initial state. An example of uncertainty in the initial state would be that some state dimensions are unknown --- marginalizing them out gives you stochastic dynamics.
A: This is an answer to the title of the question

Where does entropy-increasing waste heat go during non-reversible processes?

The "waste heat " goes to black body radiation. This radiation is only modeled correctly with quantum mechanics.
A lot of the energy will go into the kinetic energy of the particles in the medium studied, raising the temperature.
The simple model you have in the content seems to me to be reversible.
