Does an increase in entropy always result in an increase in heat, or can there be increased entropy without an increase in heat? Most situations I can think of where entropy increases also results in an increase in heat, but just wondering if that is a rule. Are there any cases where heat does not increase with entropy?
 A: When non-uniform density gradients in a system are smoothed out entropy increases, without any generation of heat. You may also consider free expansion of an ideal gas, which is a simpler example.
A: *

*If you have a room with oxygen in one half and nitrogen in the other half, and you now remove the wall between them, then they start mixing more and more. Entropy increases. Before, you knew exactly which atoms you pointed at, when you pointed somewhere, but the more time that passes, the less sure you are of which is where. Chaos increases. Entropy increases. No heat is exchanged. 


No, heat is not a necessity for entropy change. Entropy describes any process. Entropy can certainly increase in isothermal processes as well. 
A: In addition to the answer provided by @Deep, there are situations where a system can have negative temperature. In such situations, the system can release heat and increase entropy. This can happen when there is a maximum energy that some degree of freedom of the parts of the system can assume. The canonical example from textbooks is to imagine the atoms of a paramagnetic substance in a magnetic field. The stronger the field applied, the more the electrons in the substance will align with the field until it nears saturation (i.e. all of the electrons are aligned). If you were to suddenly reverse the field, the electrons would now be in a higher energy state than they can reach with heating, and will have negative temperature. As the electrons fall to lower energy levels, the material will pass through the maximally disordered state (where electrons are with/against the field with 50% probability), thus the entropy will increase as it cools until it passes through the maximum entropy state. This is why negative temperature systems can be thought, formally, as being "hotter" than infinite temperature ones.
A: Your question has one unclear definition: heat. I guess that is temperature. 
Here is one simple example. A box is filled with gas and the box wall is well insulated. If, somehow, the box volume can be doubled, the entropy increases and the gas temperature decreases.  
