ORA-01653 Unable to Extend Table AGILE.A_DW_TXN_LOG BY 128 in Tablespace AGILE_DATA3

Deleting data will not make any difference as Oracle will have kept the space ready to be re-filled. The top space usage in a table is known as the high water mark. Tom Kyte has a great post about it.

You reduce the high water mark by rebuilding the table:

alter table my_table_name move;

If you're still getting the error after increasing the size of the tablespace there are a couple of possible reasons...

1. The index is too big even for the newly increased tablespace. How big is the table and what are the combined size of the columns you're indexing?
2. You're not specifying a tablespace when creating the index and it's not using the one you think, whatever the default tablespace for your schema is.

The answer to 1 to is add more space.

To find out your default tablespace:

select * from dba_users where username = 'MY_USER'

If this is not your index tablespace you have to specify it when creating the index.

create index i_my_table 
    on my_table ( my_column ) 
       tablespace my_index_ts
       < other options >

Yes, if you're in 9i it's definitely worth collecting statistics as it doesn't collect them automatically when enough changes have been made to the table - it does in later versions. Use DBMS_STATS.GATHER_TABLE_STATS() and only do this after rebuilding the table.

Unfortunately in Oracle you can't reduce the size of a tablespace. To use this option you'd have to re-create the tablespace, but smaller, and move everything to it.

Seems like you have media corruption. I would consult Automatic Diagnostic Repository (ADR) contents if there are open failures in your database. You can do that via Enterprise Manager or using RMAN command-line utility:

[oracle@oca ~]$ rman target=/

RMAN> list faliure;

If there are failures with status OPEN listed, you can ask Data Recovery Advisor (DRA) to analyze them and recommend you the solution to repair the failures:

RMAN> advise failure;

Since you have block corruption, DRA will probably suggest you to recover the corrupted blocks and will create the appropriate script which you can run manually or in the same flow with RMAN:

RMAN> repair failure;

After failures are repaired they're automatically closed by DRA. You can check if all failures are closed with one more list failure command in RMAN, and if not you can get another advice from DRA.

EDIT:

Since the recovery you performed didn't last long (elapsed time: 00:00:00), I infer that the datafile wasn't written to by RMAN, and maybe even checked. Thus I would recommend you to proactively validate the database; to do that, just issue validate database in RMAN and analyze the output. RMAN will check all datafiles (including control file and spfile) and show you if there are any corrupted blocks.

In your comment, you said that RMAN returns the message "Block Media Recovery requires Enterprise Edition" in response to one of your commands, and based on the response from RMAN to validate database command I suspect this feature is also not available in your software edition. If your database is running in ARCHIVELOG mode (check with select log_mode from v$database) you could just completely restore and recover your database without loss of committed transaction, but before doing this I would make sure that your media (hard disk) is not damaged.