Here are several options, all with different ways of going from wide to long data. Each time, you need to do some operation twice, because you are turning the scores into long data, and turning the letters into long data. Beyond that, it's a matter of preference how you want to write your code.
First is with dplyr and tidyr, where you can use gather and pipe your data through in a single statement. The select lets you change the names to V1 and V2.
library(tidyverse)
df_long_gather <- df %>%
  gather(key = key1, value = letter, V1:V3) %>%
  gather(key = key2, value = score, V4:V6) %>%
  select(V1 = letter, V2 = score) %>%
  arrange(V1)
head(df_long_gather)
#> # A tibble: 6 x 2
#>   V1       V2
#>   <chr> <int>
#> 1 A        45
#> 2 A        78
#> 3 A        39
#> 4 B        45
#> 5 B        23
#> 6 B        78
You can also use melt from reshape2. You can do this in two steps (first version), or nest one call inside another to do in one step (second version). You can also use the %>% pipes to use both melts in a single statement.
Two steps: 
library(reshape2)
melted1 <- melt(df, id.vars = c("V1", "V2", "V3"), 
    measure.vars = c("V4", "V5", "V6"), variable.name = "key1", 
    value.name = "score")
melted2 <- melt(melted1, measure.vars = c("V1", "V2", "V3"), 
    variable.name = "key2", value.name = "V1")
df_long_melt <- data.frame(V1 = melted2$V1, V2 = melted2$score)
head(df_long_melt)
#>   V1 V2
#> 1  A 45
#> 2  E 12
#> 3  E 23
#> 4  H 23
#> 5  A 78
#> 6  E 42
One step:
df_long_melt2 <- melt(
    melt(df, measure.vars = c("V1", "V2", "V3"), value.name = "key1"),
    measure.vars = c("V4", "V5", "V6"), value.name = "key2")[, c(2, 4)]
names(df_long_melt2) <- c("V1", "V2")
head(df_long_melt2)
#>   V1 V2
#> 1  A 45
#> 2  E 12
#> 3  E 23
#> 4  H 23
#> 5  B 45
#> 6  F 12