Canonically deformed spacetime, where the commutator of two coordinates is a constant, is the most commonly studied noncommutative space. Noncommutative gauge theories that have ordinary gauge theory as their commutative limit have been constructed there. But these theories have their drawbacks: First of all, constant noncommutativity can only be an approximation of a realistic theory, and therefore it is necessary to study more complicated space-dependent structures as well. Secondly, in the canonical case, the noncommutativity didn't fulfill the initial hope of curing the divergencies of quantum field theory. Therefore it is very desirable to understand noncommutative spaces that really admit finite QFTs. These two aspects of going beyond the canonical case will be the main focus of this thesis. They will be addressed within two different formalisms, each of which is especially suited for the purpose. In the first part noncommutative spaces created by star-products are studied. In the case of nonconstant noncommutativity, the ordinary derivatives possess a deformed Leibniz rule, i.e. d_i (f star g) \neq d_i f star g + f star d_i g. Therefore we construct new objects that still have an undeformed Leibniz rule. These derivations of the star-product algebra can be gauged much in the same way as in the canonical case and lead to function-valued gauge fields. By linking the derivations to frames (vielbeins) of a curved manifold, it is possible to formulate noncommutative gauge theories that admit nonconstant noncommutativity and go to gauge theory on curved spacetime in the commutative limit. We are also able to express the dependence of the noncommutative quantities on their corresponding commutative counterparts by using Seiberg-Witten maps. In the second part we will study noncommutative gauge theory in the matrix theory approach. There, the noncommutative space is the ground state of a matrix action, the fluctuations around this ground state creating the gauge theory. In the canonical case the matrices used are infinite-dimensional (they are the Fock-space representation of the Heisenberg algebra), leading to a number of problems, especially with divergencies. Therefore we construct gauge theory using finite dimensional matrices (fuzzy spaces). This gauge theory is finite, goes to gauge theory on a 4-dimensional manifold in the commutative limit and can also be used to regularize the noncommutative gauge theory of the canonical case. In particular, we are able to match parts of the known instanton sector of the canonical case with the instantons of the finite theory.