Eso sucede porque cuando haces un append(datos), en lugar de agregar los elementos de datos, guardas una referencia al objeto datos. Por eso cuando modificas o eliminas datos, tambien cambia el contenido de Informacion.
Una forma de hacer lo que quieres sin modificar mucho el código sería:
Informacion = []
x = int(input("Cuantos datos desea introducir: "))
for i in range(x):
nombre = raw_input("Nombre: ")
edad = raw_input("Edad: ")
Informacion.append([nombre, edad])
print("los datos son",Informacion)
Para recorrer la lista, puedes usar un for:
for datos in Informacion:
print "Nombre:", datos[0]
print "Edad:", datos[1]
Recuerda que estás recorriendo una lista cuyo cada elemento es una lista nueva de dos elementos.
Otra forma de hacer lo mismo sería con diccionarios. Echales un vistazo.
Saludos!