It is not possible to implement error correction without adding parity bits. However, in some cases it may be possible to 'steal' some bits from some other part of the protocol. This is what is done with the FEC implementations for Ethernet.
Let's take 10GBASE-R Ethernet as an example. 10GBASE-R Ethernet without FEC is transferred using the 64b/66b line code - 64 bit data blocks are scrambled with an LFSR, then a 2 bit sync header is attached to each block, and the data is sent serially at 10.3125 Gbps. The 10GBASE-KR FEC is designed to add forward error correction while maintaining the same data rate of 10 Gbps before encoding and 10.3125 Gbps on the wire. This is done by taking 32 blocks 64b/66b encoded data, stripping off one of the sync bits on each block to free up 32 bits, adding 32 parity bits of shortened cyclic code (2112, 2080), scrambling the result, and then sending that on the wire at 10.3125 Gbps.
There are trade-offs to this approach, though: since the sync headers have been effectively removed, the block lock time is vastly increased (the PHY needs to check up to 2112 blocks at 2112 bits each instead of 66 blocks of 66 bits each), extending the time required to bring a link up by several orders of magnitude.
The newer Ethernet Reed-Solomon FEC does something similar, but with an even larger block size. 64b/66b data is transcoded four blocks at a time into 256b/257b, 20 257 bit blocks are broken up into 514 10 bit symbols, those are encoded with RS(528,514) to generate 14 10-bit parity symbols for 528 total symbols, which are then packed up and sent as a 5280 bit block. The original data, encoded with 64b/66b, would also take up 66*4*20 = 5280 bits.