How does padding oracle attack work with bytes larger than possible length?

I am trying to understand how the POODLE attack would actually be implemented. In the original security advisory from Möller, Duong and Kotowicz [POODLE 14] the following example is presented:

Assume that each block $$C$$ has 16 bytes, {..}. The MAC size in SSL 3.0 CBC cipher suites is typically 20 bytes, so below the CBC layer, an encrypted POST request will look as follows:

Then the authors go on explaining how one can decrypt a previously unknown byte of the cookie:

The attacker then replaces $$C_n$$ by $$C_i$$ and forwards this modified SSL record to the server.

I understand it so far. The only problem I have is this, since the padding is 1 to L bytes long (where L is our block size in bytes, 16 in our example) we only can decrypt bytes with values between 1 and L right ? Let's say the last byte in the block $$C_i$$ equals to 0x0020, how would I decrypt it ?

For a CBC mode cipher, which is what POODLE applies to, you don't encrypt or decrypt individual bytes, but rather blocks, formed by adding padding to the actual data bytes. For encryption in general every byte can be any value 0 to 255, and the SSL spec allows the padding_length byte to be almost any value, but most if not all implementations only use 0 to L-1. (Not 1 to L; a different common padding scheme, PKCS#5/7, does use 1 to L.) SSL/TLS uses MAC-then-encrypt (see a hundred other questions why this turned out to be not the best choice) so actually user-data plus HMAC is padded and then CBC-encrypted, as shown by the line you posted: user data consisting of POST /path cookies etc, then (20-byte) MAC, then padding.

CBC mode encrypts a block at a time after XORing the plaintext block with the previous ciphertext block, or for the first block with the IV. Similarly when decrypting it XORs the decrypted block with the previous ciphertext block or IV to produce the plaintext. The diagram in Wikipedia shows this in detail.

HOW POODLE BITES. You omitted most of the paper's explanation:

The attacker controls both the request path and the request body, and thus can induce requests such that the following two conditions hold:
● The padding fills an entire block (encrypted into Cn).
● The cookies’ first as-of-yet unknown byte appears as the final byte in an earlier block (encrypted into Ci).
The attacker then replaces Cn by Ci and forwards this modified SSL record to the server. Usually, the server will reject this record, and the attacker will simply try again with a new request. Occasionally (on average, once in 256 requests), the server will accept the modified record, and the attacker will conclude that DK(Ci)[15] ⊕ Cn-1 [15] = 15, and thus that Pi[15] = 15 ⊕ Cn-1 [15] ⊕ Ci-1 [15]. This reveals the cookies’ first previously unknown byte. The attacker proceeds to the next byte by changing the sizes of request path and body simultaneously such that the request size stays the same but the position of the headers is shifted , continuing until it has decrypted as much of the cookies as desired. The expected overall effort is 256 SSL 3.0 requests per byte.

When Cn is replaced by Ci satisfying the two stated conditions, the receiver first decrypts, and unpads, the received message. There are two possibilities:

• If the result of CBC decryption has anything other than 15 in the last byte, the unpadding either fails entirely or yields a result that fails MAC verification (with overwhelming probability), producing an error alert that the attacker can observe.
• If the result of CBC decryption does have 15 in the last byte, the receiver doesn't detect any error and continues with the session. The attacker now knows that the last byte from the previous ciphertext block (Cn-1[15]) XORed with byte 15 of the block that was encrypted to form Pi (Dk(Ci)[15]) is 15 and also knows that Dk(Ci)[15] was computed as Pi[15] XOR Ci-1[15]. Combining these allows the attacker to compute Pi[15] with the formula shown.

Replace 16 and 15 by 8 and 7 for an 8-byte block cipher, which for SSLv3 was triple-DES, DES, RC2 or IDEA. But almost nobody implemented IDEA and RC2, and DES has been insecure and deprecated or prohibited for over a decade.