This dissertation considers new constructions and decoding approaches for error-correcting codes based on non-conventional polynomials, with the objective of providing new coding solutions to the applications mentioned above. With skew polynomials, we construct codes that are dual-containing, which is a desired property of quantum error-correcting codes. By considering evaluation codes based on skew polynomials, a condition on the existence of optimal support-constrained codes is derived and an application of such codes in the distributed multi-source networks is proposed. For a class of multicast networks, the advantage of vector network coding compared to scalar network coding is investigated. Multivariate polynomials have been attracting increasing interest in constructing codes with repair capabilities by accessing only a small amount of available symbols, which is required to build failure-resistant distributed storage systems. A new class of bivariate evaluation codes and their local recovery capability are studied. Interestingly, the well-known Reed-Solomon codes are used in a class of locally recoverable codes with availability (multiple disjoint recovery sets) via subspace design. Aside from new constructions, decoding approaches are considered in order to increase the error correction capability in the case where the code is fixed. In particular, new lower and upper bounds on the success probability of joint decoding interleaved alternant codes by a syndrome-based decoder are derived, where alternant codes are an important class of algebraic codes containing Goppa codes, BCH codes, and Reed-Muller codes as sub-classes.