Deep Omit with typescript

This can easily be done, you just need to use mapped types to recurse down the properties:

type Primitive = string | Function | number | boolean | Symbol | undefined | null 
type DeepOmitHelper<T, K extends keyof T> = {
    [P in K]: //extra level of indirection needed to trigger homomorhic behavior 
        T[P] extends infer TP ? // distribute over unions
        TP extends Primitive ? TP : // leave primitives and functions alone
        TP extends any[] ? DeepOmitArray<TP, K> : // Array special handling
        DeepOmit<TP, K> 
        : never
}
type DeepOmit<T, K> = T extends Primitive ? T : DeepOmitHelper<T,Exclude<keyof T, K>> 

type DeepOmitArray<T extends any[], K> = {
    [P in keyof T]: DeepOmit<T[P], K>
}
type Input =  {
    __typename: string,
    a: string,
    nested: {
        __typename: string,
        b: string
    }
    nestedArray: Array<{
        __typename: string,
        b: string
    }>
    nestedTuple: [{
        __typename: string,
        b: string
    }]
}

type InputWithoutKey = DeepOmit<Input, '__typename'>

let s: InputWithoutKey = {
    a: "",
    nested: {
        b:""
    },
    nestedArray: [
        {b: ""}
    ],
    nestedTuple: [
        { b: ""},
    ]
}

Just a caveat, this works on 3.4, the handling of mapped types on arrays and tuples has changed recently, so depending on version you might need to handle arrays as a special case.

The answers here were inspiring. I had some small issues with TypeScript 4.0 that I was able to work out. I'm maintaining it as a gist: https://gist.github.com/ahuggins-nhs/826906a58e4c1e59306bc0792e7826d1. Hope this helps some people, especially those wanting to deal with Partial utility in a deep omit.

/** Union of primitives to skip with deep omit utilities. */
type Primitive = string | Function | number | boolean | Symbol | undefined | null

/** Deeply omit members of an array of interface or array of type. */
export type DeepOmitArray<T extends any[], K> = {
    [P in keyof T]: DeepOmit<T[P], K>
}

/** Deeply omit members of an interface or type. */
export type DeepOmit<T, K> = T extends Primitive ? T : {
    [P in Exclude<keyof T, K>]: //extra level of indirection needed to trigger homomorhic behavior
        T[P] extends infer TP ? // distribute over unions
        TP extends Primitive ? TP : // leave primitives and functions alone
        TP extends any[] ? DeepOmitArray<TP, K> : // Array special handling
        DeepOmit<TP, K>
        : never
}

/** Deeply omit members of an array of interface or array of type, making all members optional. */
export type PartialDeepOmitArray<T extends any[], K> = Partial<{
    [P in Partial<keyof T>]: Partial<PartialDeepOmit<T[P], K>>
}>

/** Deeply omit members of an interface or type, making all members optional. */
export type PartialDeepOmit<T, K> = T extends Primitive ? T : Partial<{
    [P in Exclude<keyof T, K>]: //extra level of indirection needed to trigger homomorhic behavior
        T[P] extends infer TP ? // distribute over unions
        TP extends Primitive ? TP : // leave primitives and functions alone
        TP extends any[] ? PartialDeepOmitArray<TP, K> : // Array special handling
        Partial<PartialDeepOmit<TP, K>>
        : never
}>

For those coming here with a later version of TS (I've tested this with TS3.8.3), you'll need to inline DeepOmitHelper from Titian's answer.

type Primitive =
  | string
  | Function
  | number
  | boolean
  | Symbol
  | undefined
  | null;

type DeepOmitArray<T extends any[], K> = {
  [P in keyof T]: DeepOmit<T[P], K>;
};

export type DeepOmit<T, K> = T extends Primitive
  ? T
  : {
      [P in Exclude<keyof T, K>]: T[P] extends infer TP
        ? TP extends Primitive
          ? TP // leave primitives and functions alone
          : TP extends any[]
          ? DeepOmitArray<TP, K> // Array special handling
          : DeepOmit<TP, K>
        : never;
    };