This issue also prevents trying to build Python with gcc on AIX which I am attempting at the moment.
While trying to resolve my own issue I have applied the following dirty patch to the python-2.5 tar ball.
The patch should allow you to set CC to a non standard value.

# Patch to make Python work with AIX and OpenPKG.
#
# This patch is NOT complete.
# - configure is not automatically recreated from configure.in
# - The correct behaviour for AIX should be to use CC if set and
#   otherwise to look for cc_r, cc and gcc (not sure about the order).
#
Index: configure.in
--- configure.in.orig   2007-02-19 15:19:32.000000000 +0100
+++ configure.in        2007-02-19 15:21:35.000000000 +0100
@@ -346,8 +346,15 @@
                without_gcc=$withval;;
        esac], [
        case $ac_sys_system in
-       AIX*)   CC=cc_r
-               without_gcc=;;
+       AIX*)
+               # set CC if not set already.
+               # - SHOULD enhance check to look for cc or gcc in case it
+               #   is in the PATH.
+               if /usr/bin/test -z "$CC"; then
+                       CC=cc_r
+                       without_gcc=
+               fi
+               ;;
        BeOS*)
                case $BE_HOST_CPU in
                ppc)
Index: configure
*** configure.orig      Tue Feb 20 10:14:18 2007
--- configure           Tue Feb 20 10:15:23 2007
***************
*** 1719,1726 ****
  else

        case $ac_sys_system in
!       AIX*)   CC=cc_r
!               without_gcc=;;
        BeOS*)
                case $BE_HOST_CPU in
                ppc)
--- 1719,1733 ----
  else

        case $ac_sys_system in
!       AIX*)
!               # set CC if not set already.
!               # - SHOULD enhance check to look for cc or gcc in case it
!               #   is in the PATH.
!               if /usr/bin/test -z "$CC"; then
!                       CC=cc_r
!                       without_gcc=
!               fi
!               ;;
        BeOS*)
                case $BE_HOST_CPU in
                ppc)